[BOJ/백준] 31434 - 당근 클릭 게임

31434번: 당근 클릭 게임

---

2차원 DP

---

---

• 제목

당근 클릭 게임

---

• 조건

시간 제한 : 2 초

메모리 제한 : 1024 MB 

---

• 문제

에릭은 방학 동안 너무 심심한 나머지, 당근 클릭 게임이라는 게임을 직접 만들어서 플레이하기로 했다.

이 게임에서 초기에 에릭은 당근을 0개 가지고 있고, s가 1인 상태로 게임을 시작한다.

그 후, 매초 다음 두 가지의 행동 중 하나를 할 수 있다.

1. 마우스를 클릭하고 당근을 s개 얻는다.
2. 정수 i(1 ≤ i ≤ N)를 고르고, 당근 Ai개를 지불하여 i번째 스피드 효과를 구매한다. 구매 직후, s가 Bi만큼 증가한다. (이전에 구매한 스피드 효과를 다시 구매하는 것도 가능하다.)

게임을 개발하느라 에너지를 모두 소모해 버린 에릭을 위해 게임을 
K초 플레이한 후 당근을 최대 몇 개까지 가지고 있을 수 있는지 알려주자!

---

• 입력

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

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

---

• 출력

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

---

• 힌트

1 ≤ N, K ≤ 100$
 
1 ≤ Ai, Bi ≤ 50 

---

예제 입력1	예제 출력1
2 4 1 2 2 5	6

---

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer st;

    static class CARROT {
        int cost;
        int effect;

        public CARROT(int cost, int effect) {
            this.cost = cost;
            this.effect = effect;
        }
    }

    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        ArrayList<CARROT> carrots = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int cost = Integer.parseInt(st.nextToken());
            int effect = Integer.parseInt(st.nextToken());
            carrots.add(new CARROT(cost, effect));
        }

        int answer = 0;
        int[][] dp = new int[K + 1][50 * 100 + 1];
        boolean[][] able = new boolean[K + 1][50 * 100 + 1];
        able[0][1] = true;
        for (int i = 1; i <= K; i++) {
            for (int j = 1; j <= 5000; j++) {

                if(able[i - 1][j]){
                    dp[i][j] = dp[i - 1][j] + j;
                    able[i][j] = true;
                }
                for (int k = 0; k < carrots.size(); k++) {
                    int cost = carrots.get(k).cost;
                    int effect = carrots.get(k).effect;
                    if(j - effect <= 0) continue;
                    if(dp[i - 1][j - effect] - cost < 0) continue;
                    if(able[i - 1][j - effect]){
                        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - effect] - cost);
                        able[i][j] = true;
                    }
                }
                answer = Math.max(answer, dp[i][j]);
            }
        }
        System.out.println(answer);
    }
}