[백준 - 31434번] 당근 클릭 게임 - Java

문제 링크

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

문제

티어: 골드 3
알고리즘: dp

입력

첫 번째 줄에 두 정수 $N$, $K$가 공백으로 구분되어 주어진다.

다음 $N$개의 줄 중 $i$번째 줄에 두 정수 $A_i$, $B_i$가 공백으로 구분되어 주어진다.

출력

에릭이 게임을 $K$초 플레이한 후 최대로 가지고 있을 수 있는 당근의 개수를 출력한다.

풀이

에릭이 게임을 K초 플레이한 후 최대로 가질 수 있는 당근의 개수를 출력해야 한다.

완전 탐색부터 적용해 보면, 매번 선택할 수 있는 경우의 수가 N + 1개 이기 때문에 s^(N+1)로 불가능하다.

그러면 최선의 선택이 있을까? 최선의 선택 기준이 애매하다. 단순히 당근을 최대로 얻는 선택은 가능하지만, 당근보다 s의 크기를 증가시키는 것이 더 나은 선택이 될 수 있다. 그래서 그리디도 아니다.

결국 가능한 경우를 탐색해야 최대 개수를 구할 수 있기 때문에 dp 문제임을 알 수 있다.

어떤 경우에서 선택지는 N + 1이지만, 선택을 했을 때 될 수 있는 상태는 최대 5000개다.
여기서 상태는 초와 s로 판단이 된다. 이 상태가 같다면 당연히 당근의 개수가 많은 쪽이 유리하다. 그래서 우리는 매 초마다 경우의 수를 5000개로 유지해 줄 수 있다.

이를 토대로 dp를 정의하고 구현하면 된다.
dp[A][B] -> A는 초고, B는 s의 크기다. (s의 최대 크기는 단순히 50 * 100으로 구했다.)

이 풀이의 시간 복잡도는 O(K 5000 N)이다.

소스 코드

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

public class Main {
    static int N,K;
  public static void main(String args[]) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      N = Integer.parseInt(st.nextToken());
      K = Integer.parseInt(st.nextToken());
      int[][] dp = new int[K + 1][5001]; //[A][B] A는 초, B는 S
      int[][] item = new int[N][2]; //0은 당근 지불 개수, 1은 스피드 증가수
      for(int i=0; i<N; i++) {
          StringTokenizer st2 = new StringTokenizer(br.readLine());
          item[i][0] = Integer.parseInt(st2.nextToken());
          item[i][1] = Integer.parseInt(st2.nextToken());
      }
      init(dp);
      dp[1][1] = 1; //0초에서는 마우스 클릭이라는 선택지밖에 없음
      
      //100 * 5000 * 100
      for(int i=2; i<=K; i++) {
          for(int j=0; j<=5000; j++) {
              if(dp[i - 1][j] != -1) {
                  //전의 경우의 수가 존재한다면
                  //마우스 클릭
                  dp[i][j] = Math.max(dp[i][j], dp[i - 1][j] + j);
                  //아이템 사용
                  for(int ind = 0; ind < N; ind++) {
                      if(dp[i - 1][j] >= item[ind][0]) {
                          //당근을 지불할 수 있다면
                          dp[i][j + item[ind][1]] = Math.max(dp[i][j + item[ind][1]], dp[i - 1][j] - item[ind][0]);
                      }
                  }
              }
          }
      }
      
      int answer = -1;
      for(int i=0; i<=5000; i++) {
          answer = Math.max(answer, dp[K][i]);
      }
      System.out.println(answer);
  }
  
  static void init(int[][] dp) {
      for(int i=1; i<dp.length; i++) {
          for(int j=0; j<dp[i].length; j++) {
              dp[i][j] = -1;
          }
      }
  }
}