[백준 / 실버1] 15486 퇴사 2

Ilhwanee·2022년 9월 8일
0

코딩테스트

목록 보기
91/155
post-custom-banner

문제 보기



사용한 것

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


풀이 방법

  • 뒤에서 부터 계산
  • i 번째 날의 예약이 기한 안에 (n + 1보다 같거나 작음) 끝낼 수 없으면 dp[i] = dp[i + 1]
  • 끝낼 수 있으면 p[i] + dp[i + t[i]]와 dp[i + 1] 중 큰 값을 dp[i]에 저장
    • 전자는 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[] t = new int[n + 1];
        int[] p = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            String[] line = br.readLine().split(" ");
            t[i] = Integer.parseInt(line[0]);
            p[i] = Integer.parseInt(line[1]);
        }

        int[] dp = new int[n + 2];
        for (int i = n; i >= 1; i--) {
            if (i + t[i] > n + 1) {
                dp[i] = dp[i + 1];
            } else {
                dp[i] = Math.max(p[i] + dp[i + t[i]], dp[i + 1]);
            }
        }

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


profile
블로그 이전 -> https://pppp0722.github.io
post-custom-banner

0개의 댓글