아이디어

• 숫자를 고르는 최소 횟수를 DP로 구한다.
  • 숫자 i를 만드는 데 필요한 수의 개수 = 숫자 (i-마지막으로 사용한 정수)를 만드는 데 필요한 수의 개수 + 1[마지막으로 사용한 정수]
• 구하는 중 횟수가 K를 넘어가면 해당 숫자에서 승자가 결정된다. 숫자의 홀짝 여부로 승자를 구하고 승자와 숫자를 출력한다.

코드

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

public class Main {
	static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer tk = null;

	static int N, K, A[], maxA, memo[];
	
	public static void main(String[] args) throws Exception {
		N = Integer.parseInt(rd.readLine());
		
		A = new int[N];
		tk = new StringTokenizer(rd.readLine());
		for (int i=0; i<N; i++) {
			A[i] = Integer.parseInt(tk.nextToken());
			maxA = Math.max(maxA, A[i]);
		}
		
		K = Integer.parseInt(rd.readLine());
		
		memo = new int[maxA * K + 1 + 1];
		for (int i=1; i<memo.length; i++) {
			memo[i] = Integer.MAX_VALUE;
			for (int j=0; j<N; j++) {
				if (A[j] <= i) {
					memo[i] = Math.min(memo[i], memo[i-A[j]] + 1);
				}
			}
			if (memo[i] > K) {
				if (i % 2 == 0)
					sb.append("holsoon");
				else
					sb.append("jjaksoon");
				sb.append(" win at ");
				sb.append(i);

				System.out.println(sb);
				return;
			}
		}
	}
}

메모리 및 시간

• 메모리: 14048 KB
• 시간: 124 ms

리뷰

• 이 문제를 그래프 탐색으로도 풀 수 있다고 하는데, 시간이 되면 어떻게 풀 수 있을지 생각해보는 것도 좋겠다.