[백준] 숫자놀이 (1679번)

문제 힌트

 

1. 자료구조

배열을 이용한 DP (동적 계획법) 활용

• 목적: 특정 숫자를 만들기 위한 최소 연산 횟수를 기록하여 계산 최적화
• 이유:
  • 매번 새로운 숫자를 만들 때, 이전에 계산된 최적의 값(dp[i])을 활용하면 중복 연산을 피할 수 있음

최댓값 기반 DP 테이블 크기 설정

• 방법: dp[max * K + 1] 크기의 배열 생성
• 이유:
  • 주어진 숫자들을 조합하여 만들 수 있는 최대값은 max * K
  • +1을 추가하여 배열 인덱스를 다루기 쉽게 설정

 

2. 핵심 아이디어

1부터 최댓값까지 반복 탐색

• 1부터 최댓값(max * K + 1)까지 순차적으로 확인
• 현재 숫자를 만들기 위한 최소 연산 횟수(dp 값)을 계산
• dp[i] > K가 되는 순간, 게임 종료

사용할 수 있는 숫자 방문

• 오름차순 정렬된 사용 가능한 숫자 배열을 순회하며 최적의 방법 탐색
• 각 숫자를 조합하여 만들 수 있는 값을 dp 배열에 기록

점화식 활용 (DP)

• dp[i] = min(dp[i], dp[i - availableNum[j]] + 1)
• 현재 숫자 i를 만들기 위해, i - availableNum[j]의 값(dp[i - availableNum[j]])을 참고하여 최소 횟수 갱신

예시 (사용 가능한 숫자: 1, 3)

1. dp[1] = 1 (1을 만드는 데 1번 사용)
2. dp[2] = dp[1] + 1 (dp[2 - 1] + 1, 즉 dp[1] + 1)
3. dp[3] = dp[2] + 1 (dp[3 - 1] + 1, 즉 dp[2] + 1)
4. dp[3] = dp[0] + 1 (dp[3 - 3] + 1, 즉 dp[0] + 1)

즉, dp[i]는 사용 가능한 숫자 중 어떤 숫자를 활용했을 때 최소 횟수로 i를 만들 수 있는지를 저장하는 방식으로 동작함.

 

3. 로직 정리

입력 및 초기화

1. N (사용할 수 있는 숫자의 개수) 입력
2. 배열에 숫자 저장 및 최댓값 max 계산
3. dp[max * K + 1] 크기의 DP 배열 생성 및 초기화

DP 배열 채우기

1. dp[i] = Integer.MAX_VALUE로 초기화
2. availableNum[j]을 사용하여 dp[i] 값을 갱신
3. dp[i] > K가 되는 첫 순간을 찾음

승자 판별 및 출력

1. i % 2 == 0 → "holsoon win at i"
2. i % 2 == 1 → "jjaksoon win at i"

 

정답은 더보기 클릭

---

import java.util.*;
import java.io.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 입력을 빠르게 받기 위한 BufferedReader
    static StringBuilder sb = new StringBuilder(); // 문자열을 효율적으로 조작하기 위한 StringBuilder
    static StringTokenizer st;

    public static void main(String[] args) throws Exception {
        int N = Integer.parseInt(br.readLine()); // 사용 가능한 숫자의 개수
        st = new StringTokenizer(br.readLine()); // 사용 가능한 숫자들을 읽어옴
        int K = Integer.parseInt(br.readLine()); // 최대 이동 횟수

        int[] availableNum = new int[N]; // 사용할 수 있는 숫자 목록
        int max = 0; // 사용할 수 있는 숫자 중 최댓값을 저장할 변수

        for (int i = 0; i < N; i++) {
            availableNum[i] = Integer.parseInt(st.nextToken());
            max = Math.max(max, availableNum[i]); // 최댓값 업데이트
        }

        int[] dp = new int[max * K + 2]; // DP 테이블 (최소 이동 횟수를 저장)

        // DP 초기화 및 계산
        for (int i = 1; i < dp.length; i++) {
            dp[i] = Integer.MAX_VALUE; // 최소값을 찾기 위해 초기값을 매우 크게 설정

            for (int j = 0; j < N; j++) {
                if (availableNum[j] <= i) { 
                    // 현재 위치 i에서 availableNum[j]를 빼서 만들 수 있는 최소 이동 횟수를 찾음
                    dp[i] = Math.min(dp[i], dp[i - availableNum[j]] + 1);
                }
            }

            // 만약 현재 값이 K보다 크다면 승패가 결정됨
            if (dp[i] > K) {
                // i가 짝수이면 "holsoon win", 홀수이면 "jjaksoon win"
                if (i % 2 == 0) sb.append("holsoon");
                else sb.append("jjaksoon");

                sb.append(" win at ").append(i); // 승리한 값 출력

                System.out.println(sb); // 결과 출력 후 종료
                return;
            }
        }
    }
}