[백준 / 실버3] 14501 퇴사 (Java)

문제 보기

사용한 것

• 점화식을 세워 풀이하기 위한 bottom-up

풀이 방법

• i > j 일때 dp[i]는 dp[j]보다 크거나 같음
• 만약 j에 시작하는 일이 i보다 빨리 끝나거나 같으면 dp[i]는 dp[j] + infos[j][1](info[1])보다 크거나 같음
• 모든 경우들을 따져서 가장 큰 값을 dp[i]에 저장

코드

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] infos = new int[n + 1][2];
        for(int i = 1; i <= n; i++) {
            int[] info = Arrays.stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();
            infos[i] = info;
        }

        int[] dp = new int[n + 2];
        for(int i = 1; i <= n + 1; i++) {
            for(int j = 1; j < i; j++) {
                int[] info = infos[j];
                dp[i] = Math.max(dp[j], dp[i]);
                if(j + info[0] == i) {
                    dp[i] = Math.max(dp[j] + info[1], dp[i]);
                }
            }
        }

        System.out.println(dp[n + 1]);
    }
}