백준_14501_퇴사

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

나는 이문제를 다이나믹 프로그래밍으로 접근해서 풀었다.

dfs 풀이법도 있으니까 나중에 찾아서 공부해야겠다.

 

1. 일단 첫 번째 나는 dp로 풀기로 결정했기 때문에 dp 배열을 만들어준 후 각 인덱스(0을 제외한)

에 해당하는 배열 값(dp [i])을 i 일에 벌 수 있는 최대 수익이라고 놓았다.

(d [i] => i 일에 벌 수 있는 최대 수익)

점화식은 간단하게 구할 수 있다. 예를 들어 3일째 벌 수 있는 최댓값(dp [3]) 를 구하기 위해서는

 (1 일대에 벌 수 있는 최대값 + 3일째벌수있는 값), (2 일째에 벌수있는 최대값 + 3일째 벌수있는 값) 중 가장

큰 값을 구하면 된다 

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

 

2. 하지만 생각해야 할 조건이 2 가지 정도 더 있다. 위 문제를 예시를 보면 2일에 잡혀있는 상담을 하게 되면 3,4,5,6일에

잡혀있는 상담은 할 수 없다.

즉 2일에 상담을 했다면( j = 2 일) 다음 상담을 할 수 있는 일은 7 일(2 + t [2] = 7 ) 이후로부터 할 수 있는 것이다. 

if(j + t[j] <= i)

 

3. 마지막으로 N + 1일 때에는 회사에 없기 때문에 상담기간이 N 일을 넘어간다면 그날에 상담을 할 수 없다.

예를 들어 위문제에서(N = 7)  6일에는 상담기간이 4일이기 때문에 상담이 끝나면은

(6 + 4 - 1(6일도 포함하기 때문에 1일을 빼준다)) 9일이 되어 7일을 넘어가기 때문에 6일째에 상담은 할 수 없다.

이때에는 6일보다 앞선 요일 중에 수익이 가장 큰 값을 넣어주고 다음 요일로 넘어가면 된다.

if(i + t[i] <= n + 1) {
	dp[i] = p[i];}
else {
	dp[i] = max;
	continue;}

 

 

 

import java.util.Scanner;

public class Beak_joon_14501 {


	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		
		int[] t = new int[n + 1];
		int[] p = new int[n + 1];
		int[] dp = new int[n + 1];
		
    // 최대수익값이 저장될 변수
		int max = 0;
		
		for(int i = 1; i < n + 1; i++) {
			t[i] = sc.nextInt();
			p[i] = sc.nextInt();
		}
		
        
		for(int i = 1; i < n + 1; i++) {
    // i일에 상담이 가능하다면 dp[i]를 p[i]로 초기화
			if(i + t[i] <= n + 1) {
				dp[i] = p[i];
			}
    //만약 i일에 상담이 불가능하다면 현재까지 최대수익값(max) 를 넣어주고 다음요일로 넘어간다.
			else {
				dp[i] = max;
				continue;
			}
            
			for(int j = 1; j < i; j++) {
   	// 조건을 만족한다면 i 일전 요일들(j)에 p[i] 를 더한것중 최대값을 찾는다.
				if(j + t[j] <= i) {
					dp[i] = Math.max(dp[i], dp[j] + p[i]);
				}
			}
            
            
            //최대수익값 갱신
			if(max < dp[i]) {
				max = dp[i];
			}
			
		}
		
		System.out.println(max);

}
}

전체 풀이 코드이다.