[백준 15486] 퇴사 2 (java)

문제보러가기

15486번: 퇴사 2

이 문제는 DP문제로 크게 어렵지는 않았지만 나의 경우 마지막 날짜인 n일까지 일할 수 있다는 것을 놓쳐서 시간이 좀 더 걸렸던 문제였다 ㅎ,,,

 

 

 

 

 

문제풀이

-주어진 시간을 저장하는 t [] 배열과 금액을 저장하는 p [] 배열을 생성한 후 값을 저장한다.

-해당 날짜까지 받을 수 있는 최대 금액을 저장하는 dp배열을 생성한다.

-총금액 중 최대 금액을 저장하는 max를 선언한다.

-여기서 중요한 점 dp배열은 dp [n]이 아닌 dp [n+2]로 생성한다.

-> 1인 덱스부터 시작하기 때문에 +1

-> 마지막 날짜까지 포함하려면 퇴사하는 날짜(n+1일)에서 최대 금액을 찾아야 하기 때문에 +1

 

-max는 현재 날짜의 dp배열 값과 max값 중 큰 값으로 갱신한다.

-> max = Math.max(max, dp [i])

 

-dp배열에는 현재 날짜에 가질 수 있는 최댓값을 저장하므로 i일 때는 t [i]+i일에 dp값을 갱신해줘야 한다.

-> 예) 1일째 날 t [1]=3 , p [1]=10이라면 ->1,2,3일을 일하고 4일째에 10의 금액을 가질 수 있다.

-> dp [i] = Math.max(max+p [i], dp [i+t [i]])

-> 여기서 조건을 걸어줘야 할 부분은 i+t [i]가 n+1의 범위를 벗어나지 않았을 때이다.(i+t [i] <= n+1) 

   아래와 같은 문제의 조건 때문에 가능하지 않다.

    

 

 

 

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

public class Main {

	public static void main(String[] args) throws Exception{

		//퇴사2 DP
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int max = Integer.MIN_VALUE;
		int n = Integer.parseInt(br.readLine());
		int[] dp = new int[n+2];
		int[] t = new int[n+2];
		int[] p = new int[n+2];
		for(int i=1;i<=n;i++) {
			st = new StringTokenizer(br.readLine());
			t[i] = Integer.parseInt(st.nextToken());
			p[i] = Integer.parseInt(st.nextToken());
		}
		for(int i=1;i<=n+1;i++) {
        //최대금액 갱신
			max = Math.max(max, dp[i]);
			
            //dp배열 채워줌
			if(i+t[i] <= n+1)
				dp[i+t[i]] = Math.max(max+p[i], dp[i+t[i]]);
			
		}
		System.out.println(max);
		
	}

}