퇴사 2

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

풀이

처음에는 백트래킹을 통해 얻을 수 있는 페이를 모두 계산해 최대를 구하려고 했다. 하지만 코드가 의도대로 동작하지 않았고 디버깅에 어려움이 있어 다른 방법을 생각하고 있었다.

문제의 분류에 dp가 있어서 dp로 풀어보기로 했다.

하지만 그래도 쉽지 않았고 다른 사람의 점화식을 참고했다.(dp 너무 어렵다... ㅠㅠ)

현재 일(i)에서 상담일(t)을 더해 범위(n)를 초과하지 않는 경우 금액(p)을 더해준다.
if (i + t <= n) dp[i] = max(dp[i + t], dp[i + t] + p)

하지만 위 점화식을 사용을 하면 아래와 같은 결과를 얻는다.
[0, 0, 0, 10, 30, 0, 45, 0]
상담은 매일 하기때문에 6일에 버는 돈이 0으로 나오면 안된다.

따라서 dp[i + 1] = max(dp[i + 1],dp[i])를 해줘야 한다.

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;

public class Main {
    static int n, s;
    static int ans = 0;
    static ArrayList<Pair> arr;
    static int[] dp;

    public static void main(String[] args) throws Exception {
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        n = Integer.parseInt(br.readLine());
        arr = new ArrayList<>();
        dp = new int[n + 1];

        for (int i = 0; i < n; i++) {
            String[] line = br.readLine().split(" ");
            arr.add(new Pair(Integer.parseInt(line[0]), Integer.parseInt(line[1])));
        }

        for (int i = 0; i < n; i++) {
            Pair p = arr.get(i);
            if (i + p.time <= n) {
                dp[i + p.time] = Math.max(dp[i + p.time], dp[i] + p.pay);
            }
            dp[i + 1] = Math.max(dp[i + 1], dp[i]);
        }

        ans = dp[n];
        
        bw.write(ans + "\n");
        bw.flush();
        br.close();
        bw.close();
    }
}

class Pair {
    int time;
    int pay;

    public Pair(int time, int pay) {
        this.time = time;
        this.pay = pay;
    }
}