문제 설명

문제 링크는 여기

14501번: 퇴사

---

백준이가 퇴사하기 전날까지 최대로 벌 수 있는 금액을 구하면 된다.

각각의 일은 기간과 금액이 정해져있다. 하나의 일이 끝나기 전에는 다른 일을 할 수 없다.

이때 백준이는 N+1일에는 출근할 수 없음을 고려하여 최대의 금액을 구한다.

접근

각각의 일은 두 가지 케이스로 볼 수 있다. 한다 와 안한다 . 따라서 두 가지 케이스 내 최적의 값을 가져와 비교하고, 둘 중 더 최적의 값을 선택하면 된다.

나는 아래와 같은 DP 점화식을 작성하였다.

public static int DP(int idx) {
	// 퇴근 후에도 일해야하는 경우(N 초과)
	if(idx>=N) return 0;

	// 아직 최적 값을 구하지 못한 경우
	if(cnt[idx]==-1) {

		// 일단 일을 할 수 있는지 확인
		int temp = idx+arr[idx][0];
		// 할 수 있다면
		if(temp<=N) {
			// 일단 해서 저장
			cnt[idx] = arr[idx][1] + DP(temp);
		}
		// 안한 경우 포함하여 가장 최적의 값을 저장
		cnt[idx] = Math.max(DP(idx+1), cnt[idx]);			
	}

	// 저장된 최적의 값 반환
	return cnt[idx];
}

소스코드

최종적으로 제출한 코드는 다음과 같다.

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

// 퇴사

public class Main {
	public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	public static int N;
	public static int[][] arr;
	public static int[] cnt;
	public static StringTokenizer token;
	
	public static void main(String[] args) throws Exception {
		N = Integer.parseInt(br.readLine());
		arr = new int[N][2];
		cnt = new int [N];
		
		for(int n=0; n<N; n++) {
			cnt[n] = -1;
			token = new StringTokenizer(br.readLine());
			arr[n][0] = Integer.parseInt(token.nextToken());
			arr[n][1] = Integer.parseInt(token.nextToken());
		}
		System.out.println(DP(0));
	}
	
	public static int DP(int idx) {
		if(idx>=N) return 0;
		if(cnt[idx]==-1) {
			int temp = idx+arr[idx][0];
			if(temp<=N) {
				cnt[idx] = arr[idx][1] + DP(temp);
			}
			cnt[idx] = Math.max(DP(idx+1), cnt[idx]);			
		}
		return cnt[idx];
	}
}

결과

제출 결과는 다음과 같았다.

고찰

사실 보자마자 점화식 구상은 끝났는데, 디버깅이 약간 걸렸다. 처음에는 아래와 같이 코드를 작성했었다.

	public static int DP(int idx) {
		if(idx>=N) return 0;
		if(cnt[idx]==-1) {
			// 어쩌피 idx+arr[idx][0]가 N+1보다 크면 0이겠지?
			int temp = DP(idx+arr[idx][0]);
			if(temp>0) {
				cnt[idx] = arr[idx][1] + temp;
			}
			cnt[idx] = Math.max(DP(idx+1), cnt[idx]);			
		}
		return cnt[idx];
	}

그런데 이렇게 하면 무조건 0이 나온다. 디버깅 해보니까 temp>0 조건문을 통과할 수 없게 되어 버린다… 사실 완전히 왜 그렇게 되는지 아직도 이해가 되지 않는다.

그리고 만약에 이것이 내가 원하는대로 된다고 한들, N번째 날에 수행기간이 1인 경우 처리가 가능한데, 이런 로직으로는 이를 처리 불가능으로 인지해서 코드를 최종 코드와 같이 변경하게 되었다.