백준 15486 퇴사2

문제

풀이

1. 테이블 정의

   dp[i] : i-1일까지 벌 수 있는 돈의 최댓값. i일의 0시 정도로 생각

만약 3일까지 일해서 돈을 받는다면 4일에 받는다.
dp[4] = 3

2. 점화식
   i일이 되는 순간 할 수 있는건 두가지이다.
   (원래 있던 값이 더 크다면 갱신을 하면 안되기 때문에 max를 써줘야한다.)
   

• i일에 들어오는 일을 한다.
  end = i + t[i]
dp[end] = Math.max(dp[end], dp[i] + money[i])
  
• i일에 들어오는 일을 하지 않는다.
  dp[i] = Math.max(dp[i], dp[i-1)

코드

public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int[] t = new int[n + 1];
        int[] p = new int[n + 1];
        int[] dp = new int[n + 2];


        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            t[i] = Integer.parseInt(st.nextToken());
            p[i] = Integer.parseInt(st.nextToken());
        }

        // dp[i] : i-1일까지 벌 수 있는 돈 최댓값. i일째 아직 행동을 취하지 않은 상태
        // dp[i+k] = dp[i] + pi

        for (int i = 1; i <= n; i++) {
            if (i <= n+1) dp[i+1] = Math.max(dp[i], dp[i+1]);
            int end = i + t[i];
            if (end <= n+1) dp[end] = Math.max(dp[end], dp[i] + p[i]);
        }
        System.out.println(dp[n+1]);
    }