[백준 14501] 퇴사 -Java

문제에서 2가지만 생각하면 된다
1.완전탐색으로 모든 경우의 수 를 생각한다
2.다음요일을 찾는과정에서 지나온 요일을 생각해야한다(더해준다)

처음에 2번을 생각못해서 오래걸렸다...아무튼
코드 구현은 다음과 같다

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

public class Main {

	static int[] t, p;
	static int start, n, result = Integer.MIN_VALUE;

	static void dfs(int num, int num2) {

		// num2의 합이 n을 초과 할 경우 리턴
		if (num2 > n) {
			return;
		}
		// num2의 합이 n일인 경우 포함시킨다.
		if (num2 == n) {
			result = Math.max(result, num);
		}

		// j = n일의 기간 중, 중간 부터 시작일이 되는 경우, 지난 일 수 를 받아온다
		int j = start;
		for(int i = start+num2; i < n; i++, j++) {
			// 다음 날로 넘어가는 경우 j+1일을 포함시킨다
			dfs(num + p[i], num2 + t[i] + j);
			result = Math.max(result, num);
		}

	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		n = Integer.parseInt(br.readLine());
		t = new int[n];
		p = new int[n];

		for(int i = 0 ; i < n ; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			t[i] = Integer.parseInt(st.nextToken());
			p[i] = Integer.parseInt(st.nextToken());
		}
		
		for(int i = 0; i < n; i++) {
			start = i;
			dfs(0,0);
		}
		
		System.out.print(result);		
	}
}

다른 사람들 풀이를 보니
DP로 많이 푼 것 같다. 아래의 코드를 이용하면 된다.
(dp를 많이 풀어봐야겠다..)

		//dp : N일에 얻을 수 있는 최대 수익
		int[] dp = new int[n+1];
		
		//점화식
		//현재 날짜에서 소요 시간과 비용을 더해 dp에 저장한다.
		//이후, 중복될 때 최대값을 넣는다.
		//dp[i + t[i]] = max(dp[i + t[i]], dp[i] + p[i]);
		
        // 0부터 시작(다음날로 넘어가는 경우임)
		for (int i=0; i<n; i++) {
        	// 날짜가 범위를 넘어가지 않는 경우 최대값 찾기
			if (i + t[i] <= n) {
                // 현재날짜의 소요시간 dp[i+t[i]]에서의 비용 =
                // Math.max(현재날짜의 소요시간 들어갈 비용, 현재 날짜 dp에서의(이전의) 비용 + 현재날짜 비용)
                // 즉, dp에(날짜 + 소요시간이 중복될때) 비용을 중복해서 최대값을 만든다
				dp[i + t[i]] = Math.max(dp[i + t[i]], dp[i] + p[i]);
			}

			//현재 경우의 수가 0일 수 있기 때문에 이전의 최대값을 계속해서 넣어줌.
			//해당 날짜에 일할 수 없다면, 이전까지 일한 최대 수당을 넣어주어야 한다.
			dp[i+1] = Math.max(dp[i+1], dp[i]);
		}
		System.out.println(dp[n]);