DP, DFS [BOJ14501] 퇴사

DP

DP는 top-bottom, bottom-up 의 방식으로
처음 진행되는 연산은 기록해 두고, 이미 진행했던 연산이라면 다시 연산하는 것이 아니라 기록되어 있는 값을 가져오는 방식으로 해결하는 알고리즘이다.

https://www.acmicpc.net/problem/14501
위 문제에서

가장 많이 금액을 받는 방법을 찾으려면
bottom-up의 방식으로 D-7 ~ 7일때까지 받을 수 있는 금액을 가지고 점차 앞으로 나아가 D-1~7까지 받을 수 있는 금액을 찾아나간다.

public class Bonus14501 {
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		int days[] = new int[n];
		int price[] = new int[n];
		int dp[] = new int[n+1];
		StringTokenizer st;
		
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			days[i] = Integer.parseInt(st.nextToken());
			price[i] = Integer.parseInt(st.nextToken());
		}
		
		for (int i = n-1; i >= 0; i--) {
			if(days[i]+i > n)
				dp[i] = dp[i+1];
			else {
				dp[i] = Math.max(dp[i+1], dp[i+days[i]] + price[i]);
			}
//			System.out.println(i + " is " + dp[i]);
		}
		
		System.out.println(dp[0]);
		
		
		
	}

}

제일 초기 DP[6]의 값은 마지막 날의 상담은 범위를 벗어났기에 들을 수 없으므로 DP[6+1]로 DP[7], 즉 0이다.
DP[5]에서 5번째 날의 상담은 들을 수 있다. 따라서 듣지 않고 DP[6]의 값을 가져갈지 듣고 금액을 다음에 들을 수 있는 DP[7]과 합할지를 max를 통해 결정한다.

DFS 완전탐색

다음은 코드 수는 좀 더 길어도 방법 자체는 훨씬 간략한 완전탐색 방법이다.
쉽게 말해 모든 경우의 수를 다 계산하여 최댓값의 금액을 호출해주면 된다.
모든 경우의 수는 그러면 어떻게 알 수 있을까?

백준이가 상담을 하거나 안하거나는 크게는 2가지, 구체적으로는 3가지 경우로 갈린다.

• 상담을 받아도 날짜 오버플로우가 없는 경우
  • 상담을 받는다 -> 상담 기간만큼 날짜를 이동
  • 상담을 받지 않는다 -> 다음 날짜로 이동
• 상담을 받으면 날짜가 초과되는 경우 (그림에서 7일에 상담을 받는 경우 등에 해당)
  • 상담을 받지 않는다 -> 다음 날짜로 이동

그리고 날짜 변경이 있을 때마다 위에 해당하는 코드를 반복하다가 현재 날짜가 총 날짜를 넘어가게 된다면 멈추면 된다.

package week5;

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

public class BOJ14501_퇴사 {
	
	static int days;
	static int[][] lenAndCost;
	static int max = 0;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		days = Integer.parseInt(br.readLine());
		lenAndCost = new int[days+1][2];
		
		for (int i = 1; i < days+1; i++) {
			st = new StringTokenizer(br.readLine());
			lenAndCost[i] = new int[] {Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())};
		}
		
		dfs(1,0);
		System.out.println(max);
		
	}
	
	public static void dfs(int curDay, int curMoney) {
		if(curDay>days) {
			if(curMoney>max)
				max = curMoney;
		}
		else {
			if(lenAndCost[curDay][0] + curDay <= (days+1)) {
				dfs(curDay+1,curMoney);
				dfs(curDay+lenAndCost[curDay][0], curMoney+lenAndCost[curDay][1]);
			}
			else {
				dfs(curDay+1,curMoney);
			}
		}	
	}
}

Reference

DP 풀이
https://velog.io/@chelsea/1-%EB%8F%99%EC%A0%81-%EA%B3%84%ED%9A%8D%EB%B2%95Dynamic-Programming-DP