[java] 구름톤 11일차. 통증(2)

문제

구름-그라운드 게임에는 통증이라는 시스템이 있다. 통증 수치가 높다면 게임에서 승리하기 어려워지므로, 아이템을 적절히 사용해 통증 수치를 0으로 유지하는 것이 중요하다.
게임 안에는 통증 수치를 감소시켜 주는 아이템이 2종류가 있다. 아이템의 이름은 A, B이고, 각 아이템을 사용 시 각각 Ap, Bp만큼 통증 수치를 감소시켜 준다. 각 아이템은 원하는 만큼 획득할 수 있다.
플레이어는 적과의 전투에서 피해를 입어 현재 N의 통증 수치를 가지고 있다. 플레이어가 통증 수치를 줄이기 위해 필요한 아이템의 최소 개수를 구해보자. 단, 사용했을 때 통증 수치가 0보다 작아지는 아이템은 사용할 수 없음에 유의하시오.

입력

첫째 줄에 플레이어의 통증 수치를 나타내는 정수 N이 주어진다.
둘째 줄에 아이템 A, B가 줄일 수 있는 통증 수치 Ap, Bp가 공백을 두고 주어진다.
- 2 <= N <= 10^6
- 2 <= Ap <= Bp <= 13
- Ap와 Bp는 배수 관계가 아니다.

출력

플레이어가 통증 수치를 0으로 줄이기 위해 필요한 아이템의 최소 개수를 출력한다. 단, 통증 수치를 0으로 만들 수 없는 경우에는 -1을 출력한다.

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());  // 플레이어의 통증 수치
        StringTokenizer st = new StringTokenizer(br.readLine());
        int Ap = Integer.parseInt(st.nextToken()); // 아이템 A로 줄일 수 있는 통증 수치
        int Bp = Integer.parseInt(st.nextToken()); // 아이템 B로 줄일 수 있는 통증 수치

        int minItems = Integer.MAX_VALUE; // 필요한 최소 아이템 개수 초기값 설정

        // 아이템 A만으로 통증 수치를 최대한 줄일 때부터 시작하여 아이템 B까지 사용하는 경우까지 확인
        for (int useA = 0; useA * Ap <= N; useA++) {
            int remainingPain = N - useA * Ap; // 아이템 A를 사용한 후 남은 통증 수치

            // 아이템 B를 사용하여 남은 통증 수치를 0으로 만들 수 있는지 확인
            if (remainingPain % Bp == 0) {
                int useB = remainingPain / Bp; // 아이템 B의 개수

                minItems = Math.min(minItems, useA + useB);
            }
        }

        // 아무런 조합으로 통증 수치를 0으로 만들 수 없는 경우
        if (minItems == Integer.MAX_VALUE) {
            System.out.println(-1);
        } else {
            System.out.println(minItems);
        }
    }
}

1. BufferedReader와 StringTokenizer을 사용하여 입력을 받습니다. 입력으로는 플레이어의 현재 통증 수치 N, 아이템 A로 줄일 수 있는 통증 수치 Ap, 아이템 B로 줄일 수 있는 통증 수치 Bp가 주어집니다.
2. minItems 변수를 Integer.MAX_VALUE로 초기화합니다. 이 변수는 필요한 최소 아이템 개수를 저장할 변수입니다.
3. 아이템 A만으로 통증 수치를 최대한 줄이는 경우부터 시작하여 아이템 B까지 사용하는 경우까지 확인합니다. 이를 위해 useA 변수를 0부터 N / Ap까지 반복하면서 아래 과정을 수행합니다.
   • 현재 아이템 A를 useA개 사용하였을 때, 남은 통증 수치 remainingPain을 계산합니다. 이 값은 현재 통증 수치에서 아이템 A를 사용한 횟수를 곱한 값만큼을 뺀 것입니다.
   • 남은 통증 수치 remainingPain이 아이템 B로도 줄일 수 있는 경우를 확인합니다. 이를 위해 remainingPain이 Bp로 나누어 떨어지는지를 확인하고, 나누어 떨어진다면 아이템 B를 사용한 횟수인 useB를 계산합니다.
   • 아이템 A와 B를 사용한 횟수의 합인 useA + useB가 minItems보다 작다면, 이 값을 minItems에 저장합니다.
4. 모든 경우를 확인한 후, minItems의 값이 초기화 값인 Integer.MAX_VALUE와 같다면 아무런 조합으로 통증 수치를 0으로 만들 수 없는 경우이므로 -1을 출력합니다. 그렇지 않다면 minItems를 출력합니다.

그리고 문제에 맞게 동적 프로그래밍 목적으로 코드를 작성한다면 아래와 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int Ap = Integer.parseInt(st.nextToken());
        int Bp = Integer.parseInt(st.nextToken());

        int[] dp = new int[N + 1]; // dp[i]: 통증 수치 i를 0으로 만들기 위한 최소 아이템 개수

        // 초기화
        for (int i = 1; i <= N; i++) {
            dp[i] = Integer.MAX_VALUE;
        }

        // 아이템 A로 통증 수치를 줄이는 경우
        for (int i = Ap; i <= N; i++) {
            dp[i] = Math.min(dp[i], dp[i - Ap] + 1);
        }

        // 아이템 B로 통증 수치를 줄이는 경우
        for (int i = Bp; i <= N; i++) {
            dp[i] = Math.min(dp[i], dp[i - Bp] + 1);
        }

        if (dp[N] == Integer.MAX_VALUE) {
            System.out.println(-1);
        } else {
            System.out.println(dp[N]);
        }
    }
}