백준 14501 : 퇴사 _자바 Java

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

14501번: 퇴사

---

 

	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	10	10	30	45	45	45

pi를 더해서 최대로 가져갈 수 있는 금액을 구한다. 

if(i+T[i]<=Case) {	//범위에 벗어나지 않는다면 
				 dp[i+T[i]]=Math.max(dp[i+T[i]],dp[i]+P[i]);
			 }

 

범위를 넘지 않는 선에서 금액을 더해가는 코드이다. 

예를 들어 i=0 일때, 0+t[0]=7을 넘어가지 않기 때문에  이 코드가 실행되어 dp[3]=10이 된다. 

그런데 이 코드만 계속 실행 되면 dp의 값이

0 0 0 10 0 0 0 0 
0 0 0 10 0 0 20 0 
0 0 0 10 0 0 20 0 
0 0 0 10 30 0 20 0 
0 0 0 10 30 0 45 0 
0 0 0 10 30 0 45 0 
0 0 0 10 30 0 45 0 

이렇게 변하고,누적이 되지 않는다.

예제출력 4번을 만족시키지도 않는다. 

 

dp[i+1]=Math.max(dp[i+1],dp[i]);

이 코드를 추가 해서 

매번 dp 의 값이 아래처럼 변하게 수정하였다.

 

0 0 0 10 0 0 0 0 
0 0 0 10 0 0 20 0 
0 0 0 10 0 0 20 0 
0 0 0 10 30 0 20 0 
0 0 0 10 30 30 45 0 
0 0 0 10 30 30 45 0 
0 0 0 10 30 30 45 45

---

최종 코드

import java.io.*;
import java.util.*;

public class Main {
	
	static int max=0;
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		int Case = sc.nextInt();
		int[] T = new int[Case];//소요 기간
		int[] P = new int[Case];//금액
		for(int i=0;i<Case;i++) {
			T[i]=sc.nextInt();	
			P[i]=sc.nextInt();	
		}//for
		
		int[] dp = new int[Case+1];
		
		for(int i=0;i<Case;i++) {
			 if(i+T[i]<=Case) {	//범위에 벗어나지 않는다면 
				 dp[i+T[i]]=Math.max(dp[i+T[i]],dp[i]+P[i]);	
			 }//if
			 dp[i+1]=Math.max(dp[i+1],dp[i]);	//다음dp=현재 누적값vs 다음 누적값
			 
		}//for	
		System.out.println(dp[Case]);	
	}//main()
	
}//class Main