[백준온라인] 14501번 퇴사

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

14501번: 퇴사

 

문제 요약 : 최대 이익 계산

입력	출력
1 ≤ N(일) ≤ 15 1 ≤ T(소요일) ≤ 5 1 ≤ P(이익) ≤ 1000	최대 이익

 

JAVA

채점 번호	아이디	문제 번호	결과	메모리	시간	언어	코드 길이
16353541	cbkpar	14501	맞았습니다!!	12908KB	72ms	Java	639B

import java.io.*;

public class Main {

	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n,i;
		String str = "";
		n = Integer.parseInt(br.readLine());
		int[] dp = new int[n+1];
		int[] t = new int[n];
		int[] p = new int[n];
		for(i=0;i<n;i++) {
			str = br.readLine();
			String[] arr = str.split(" ");
			t[i]=Integer.parseInt(arr[0]);
			p[i]=Integer.parseInt(arr[1]);
		}
		for(i=1;i<=n;i++) {
        //이익을 첫날부터계산하지 않고 N일부터 거꾸로 계산함
			dp[i]=Math.max(dp[i], dp[i-1]);//그 날 얻을 수 있는 이익은 그 전날 이익보다 크거나 같음
			if(t[n-i]>i) continue; // 퇴사일 보다 넘어가면 무시
			dp[i]=Math.max(dp[i], dp[i-t[n-i]]+p[n-i]); // 그날의 최댓값과 그전날의 최댓값+이익 중 큰 값으로 교체
		}
		System.out.println(dp[n]);
	}
}

예시[입력]

10

5 50

4 40

3 30

2 20

1 10

1 10

2 20

3 30

4 40

5 50

 

과정[출력]

0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0
0	0	0	30	0	0	0	0	0	0	0
0	0	0	30	30	0	0	0	0	0	0
0	0	0	30	30	40	0	0	0	0	0
0	0	0	30	30	40	50	0	0	0	0
0	0	0	30	30	40	50	60	0	0	0
0	0	0	30	30	40	50	60	70	0	0
0	0	0	30	30	40	50	60	70	80	0
0	0	0	30	30	40	50	60	70	80	90

 

 

오답노트 : dp[i]=Math.max(dp[i], dp[i-1]); 을 써주지 않으면 조건에 만족하지 않을경우 그날의 최댓값을 알 수 없다.