[백준] 14501번 : 퇴사

문제

www.acmicpc.net/problem/14501

14501번: 퇴사

문제해결방법

이 문제는 DP 배열에 날짜마다 받을 수 있는 최대 금액을 저장해서 풀었습니다.

1. 뒤에서부터 상담 일정표를 보며 DP 배열을 채워나갑니다.

예를 들어 N일에 Ti = 3, Pi = 30 이라는 상담이 있다면, DP[N+1]와 DP[N+3]+Pi을 비교해서 더 큰 값을 DP[N]에 저장합니다.

만약 상담 기간이 퇴사 일자를 넘어서 상담을 할 수 없는 경우에는 DP[N]에 DP[N+1]을 넣어줍니다.

2. DP 배열 중에 가장 큰 값이 최대 금액입니다.

코드

package baekjoon;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main14501_퇴사 {
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[][] job = new int[2][N+1];
        int[] DP = new int[N+1];
        StringTokenizer st;
        for(int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            job[0][i] = Integer.parseInt(st.nextToken());
            job[1][i] = Integer.parseInt(st.nextToken());
        }
        int max = 0;
        for(int i=N-1; i>=0; i--) {
            int curVal = 0;
            if(i+job[0][i]-1<N) curVal = DP[i+job[0][i]]+job[1][i];
            DP[i] = Math.max(DP[i+1], curVal);
            if(max < DP[i]) max = DP[i];
        }
        System.out.println(max);
    }
}

코드에 대한 피드백이나 더 좋은 아이디어는 언제나 환영입니다.