[백준 14501번][Java] 퇴사 - 재귀, for

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

14501번: 퇴사

 

재귀를 이용한 완전 탐색도 통과할 수 있습니다.

입력이 최대 15이므로 2^15가 32768이기 때문에 충분히 통과할 수 있습니다.

 

dp와 완전탐색 각각의 방식이 이 문제에서는 별다른 속도 차이를 보이지 않았습니다.

 

문제가 단순해서인지 결국 DP를 이용해 푼 방식이 재귀를 이용한 완전탐색을 그저 for문으로 바꾼 것일 뿐이었는데

DP의 정의에 대해 다시 한번 생각해보게 되네요.

 

DP라는게 그저 for문을 이용한 바텀업 방식의 완전탐색일 뿐인 아니지 않나? 라는 생각이 들었습니다.

DP의 최적 부분 구조를 찾는데 항상 애를 먹었는데, 뭔가 퍼즐 조각 하나를 찾은 느낌이네요.

일단 더 연습이 필요할 듯 합니다.

 

 

...

/*
백준 14501번 - 퇴사
https://www.acmicpc.net/problem/14501
 */
public class Main {
	static int n;
	static Schedule[] schedules;
	static int[] dp;
	public static void main(String[] args) throws IOException {
//		InputReader reader = new InputReader("testcase.txt");
		InputReader reader = new InputReader();
		n = reader.readInt();
		schedules = new Schedule[n+1];
		dp = new int[n+1];
		for (int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(reader.readLine());
			int time = Integer.parseInt(st.nextToken());
			int pay = Integer.parseInt(st.nextToken());
			schedules[i] = new Schedule(time, pay);
		}
		System.out.println(solve());
//		System.out.println(solve(1,0)); //재귀 버전
	}
	//완전탐색 재귀 버전
//	private static int solve(int i, int acc) {
//		if(i > n) return 0;
//		if(i == n) return acc;
//
// 		int ret = Math.max(solve(i + schedules[i].time, acc+schedules[i].pay) , solve(i+1, acc));;
//
//		return ret;
//	}

	private static int solve() {
		for (int i = 0; i < n; i++) {
			Schedule schedule = schedules[i];
			//선택하는 경우
			int nextIdx = i + schedule.time;
			if(nextIdx <= n) dp[nextIdx] = Math.max(dp[i] + schedule.pay, dp[nextIdx]);

			//선택하지 않는 경우
			dp[i+1] = Math.max(dp[i], dp[i+1]);
		}
		return dp[n];
	}
}
class Schedule{
	int time, pay;
	public Schedule(int time, int pay) {
		this.time = time;
		this.pay = pay;
	}
}

class InputReader {
	private BufferedReader br;

	public InputReader() {
		br = new BufferedReader(new InputStreamReader(System.in));
	}

	public InputReader(String filepath) {
		try {
			br = new BufferedReader(new FileReader(filepath));
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}
	}

	public String readLine() throws IOException {
		return br.readLine();
	}
	public int readInt() throws IOException {
		return Integer.parseInt(readLine());
	}
	public Long readLong() throws IOException {
		return Long.parseLong(readLine());
	}
}