[백준] 퇴사 (Java)

퇴사

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

 

알고리즘 선택과 근거

• DP + 누적합
  • 단순 구현으로 풀 수 있을 듯하나, DP로 푸는 게 더 좋아보임

 

정답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int days = Integer.parseInt(st.nextToken());
        int[] arr = new int[days + 1];

        for (int i = 0; i < days; i++) {
            st = new StringTokenizer(br.readLine());
            int time = Integer.parseInt(st.nextToken());
            int value = Integer.parseInt(st.nextToken());
            int after = i + time;
            if (after <= days) {
                for (int j = after; j <= days; j++) {
                    arr[j] = Math.max(arr[j], arr[i] + value);
                }
            }
        }

        System.out.println(arr[days]);
    }
}

 

 

설명

퇴사일을 넘기는 일들은 제외

일이 끝나는 날부터 끝까지 현재 인덱스 Value + 현재 일 Value 로 갱신함

단, 더 높은 값은 그대로 유지

 

마지막 인덱스 조회 시 가장 높은 Value 를 책정 할 수 있다.