[백준] 1679 - 숫자놀이(Java)

문제 파악

https://www.acmicpc.net/problem/1679

---

풀이

DP 문제이다.
동전 문제와 유사한 방법으로 풀 수 있다. (참고 : 동전)

풀이 단계는 다음과 같다.

 

DP 배열 선언 및 초기화

DP 배열은 정수를 만들기 위해 필요한 정수의 최소 사용 횟수를 저장한다.
예를 들어 DP[100]는 100원을 만들기 위해 필요한 정수의 최소 개수이다.

 

DP 배열의 최대 크기는 '가장 큰 후보 정수 * K + 2' 로 설정한다.
3,4,5 정수를 최대 10번 사용 가능하다면 51까지 연산을 필요로 한다.

 

보다 편한 연산을 위해 DP[0]은 0으로 초기화해 주고,
그 외의 원소는 '가장 큰 후보 정수 * K + 1' 로 초기화해주었다.

 

최솟값 계산

가장 작은 후보 정수부터 시작해 최솟값을 업데이트해 준다.

문제에서 친절하게도 후보 정수를 오름차순으로 정렬해 준 상태이기에 정렬은 필요 없다 👏

아래 과정을 후보 정수마다 반복하도록 한다.

 

• 후보 정수는 한 번 사용하면 해당 정수를 채울 수 있으므로 dp[num] = 1로 설정
• 주어진 후보 정수 다음(num+1)부터 시작해서 마지막 원소까지 dp 배열 업데이트
  • dp[j] = min(dp[j], dp[j-num] + dp[num])

 

이긴 후보 판단

위에서 연산한 dp 배열을 돌며 k를 초과하는 경우 승자를 출력하면 된다

---

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int givenGameNum = Integer.parseInt(br.readLine());
        StringTokenizer tok = new StringTokenizer(br.readLine(), " ");
        int k = Integer.parseInt(br.readLine());
        int[] nums = new int[givenGameNum];
        for (int i = 0; i < givenGameNum; i++) {
            nums[i] = Integer.parseInt(tok.nextToken());
        }
        final int MAX = nums[nums.length - 1] * k + 1;
        int[] dp = new int[MAX + 1];
        Arrays.fill(dp, MAX);
        dp[0] = 0;
        for (int num : nums) {
            dp[num] = 1;
            for (int j = num + 1; j <= MAX; j++) {
                dp[j] = Math.min(dp[j], dp[j - num] + dp[num]);
            }
        }
        for (int i = 1; i <= MAX; i++) {
            if (dp[i] > k) {
                System.out.println((i % 2 == 0 ? "holsoon" : "jjaksoon") + " win at " + i);
                return;
            }
        }
    }
}