[백준 14501] 퇴사

 

N일 마다 벌 수 있는 최대 이익을 저장하면서 진행한다.

 

 

dp[i] = a[i][1]; //상담 이익

dp배열의 초기값은 상담 이익으로 했다.

 

예제의 예를 들면

	1일	2일	3일	4일	5일	6일	7일
Ti	3	5	1	1	2	4	2
Pi	10	20	10	20	15	40	200

Pi 의 값을 모두 넣어준 셈인데 6일, 7일에 주어진 일은 완료할 수가 없다.

이에 대한 예외처리는 마지막에 해주었다.

 

 

1일부터 진행하며 그 날 주어진 상담을 완료할 수 있으면 dp 값을 올려준다.

n번째날의 일을 수행하여 n+1번째날의 일을 수행하지 못하면 손해가 될 수 있으므로 dp값을 업데이트 할때는

기존의 값과 비교하여 큰 값으로 갱신해주어야 한다.

if(i - j >= a[j][0])
	dp[i] = max(dp[j] + a[i][1], dp[i]);

 

위 점화식대로 진행하면 아래와 같은 표가 완성된다.

	1일	2일	3일	4일	5일	6일	7일
Ti	3	5	1	1	2	4	2
Pi	10	20	10	20	15	40	200
dp	10	20	10	30	45	70	245

 

기존 a배열의 값에 이전 날들 중 상담을 완료할 수 있으면 그 이익을 최대로 더해준 결과다.

6일, 7일 째에는 기존에 주어진 40, 200의 일을 완료할 수 없으므로 최대이익에서 제외한다.

 

 

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int a[][] = new int[n+1][2];
        int dp[] = new int[n+1];
        for(int i=1; i<=n; i++) {
            a[i][0] = sc.nextInt();
            a[i][1] = sc.nextInt();
            dp[i] = a[i][1];
        }
        
        for(int i=2; i<=n; i++)
            for(int j=1; j<i; j++)
                if(i - j >= a[j][0])
                    dp[i] = max(dp[j] + a[i][1], dp[i]);
        
        int max = 0;
        for(int i=1; i<=n; i++)
            if(i + a[i][0] <= n + 1)
                if(max < dp[i])
                    max = dp[i];
        
        System.out.println(max);
    }
    
    public static int max(int a, int b) {
        return a > b ? a : b;
    }
}