[DP&DFS] 백준 - 퇴사

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

14501번: 퇴사

 

-문제해설

이 문제는 dp를 이용해서 풀 수도 있고 dfs를 이용해서 풀 수도 있다.

두 가지 다 한 번 풀어보자!

 

먼저 dp의 경우

t, p, dp 배열의 크기를 잘 설정해야 한다.

먼저 t, p 배열의 크기는 n+2로 설정해야 한다. 그 이유는 다음과 같다.

문제 예시에서 1일의 상담기간은 3일이니깐 3일째까지는 다른 상담을 못하고 4일째부터 다른 상담을 할 수 있다.

즉 1일째의 p의 값 10은 dp[4]에 저장된다.

만약 7일째의 상담기간이 1일 경우 이 값은 dp[8]에 저장된다.

따라서 배열들의 크기는 n+1을 해줘야하고 

편의상 배열의 인덱스를 0부터 시작하는 것보다 1부터 시작하는게 일수와 매치되는게 편하므로

1 더 늘려서 배열의 크기는 n+2이다.

 

dp배열의 경우 마찬가지로 인덱스를 1부터 시작해야하므로 n+1인데 

여기서 만약 7일째의 상담기간이 최대값인 5인 경우 이 값은 dp[12]에 저장되어야 한다.

따라서 이러한 경우까지 생각해서 n+1 + 5를 해서 

dp배열의 크기는 n+6으로 설정해야 한다.

 

그 다음부터 점화식은 아래와 같다.

dp[ i+t[i] ] = Math.max( dp[ i+t[i] ], dp[i]+t[i] )

 

dp배열을 만들기 위해 아래와 같은 과정을 거치면 된다.

먼저 i=1 ~ n+1까지 순회한다.

 

먼저 dp[i] = Math.max( do[i], max ) 코드는 현재날짜까지 최대의 수익금을 dp[i]에 저장해야 한다.

 

그리고 점화식 코드의 경우

(현재날짜+상담기간)의 날짜의 수익금 =

      (현재날짜+상담기간)날짜의 기존 수익금 : 현재날짜의 수익금+현재날짜에 버는 수익금

 

을 의미한다. (말이 너무 어렵다...)

 

이를 코드로 표현한게 점화식이다.

dp[ i+t[i] ] = Math.max( dp[ i+t[i] ], dp[i]+t[i] )

 

그리고 max = Math.max( max, dp[i] )가 된다.

 

최종적으로 max를 출력해주면 된다.

 

 

 

 

다음으로 dfs 풀이의 경우이다.

아래 블로거님의 코드를 참고했다.

https://yongku.tistory.com/entry/%EB%B0%B1%EC%A4%80-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B0%B1%EC%A4%80-14501%EB%B2%88-%ED%87%B4%EC%82%AC-%EC%9E%90%EB%B0%94Java

 

 

 

 

 

 

 

 

-자바 (DP 이용)

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

public class BJ14501 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt( br.readLine() );
		
		//t와 p배열의 크기가 n+2인 이유는
		//편의상 일수와 인덱스를 맞추기 위해 1인덱스부터 시작해야 되기 때문에 n+1이 되고,
		//이제 여기서 n=7인 경우 8일까지 계산해야되기 때문에 n+2가 된다.
		int[] t = new int[n+2];
		int[] p = new int[n+2];
		
		//dp배열의 크기가 n+6인 이유는
		//마찬가지로 인덱스를 1부터 시작할거니깐 n+1인 상태에서
		//마지막날의 업무일수를 계산한 것이다.
		//n=7일 때 마지막날에 최대로 올 수 있는 상담기간 t는 5이기 때문에
		//5를 더해서 n+6의 크기를 가지는 배열이 필요하다.
		int[] dp = new int[n+6];
		int max = 0;
		
		//t와 p배열에 입력값 저장
		StringTokenizer st;
		for( int i=1; i<=n; i++ ) {
			st = new StringTokenizer( br.readLine() );
			t[i] = Integer.parseInt( st.nextToken() );
			p[i] = Integer.parseInt( st.nextToken() );
		}
		
		//1일부터 n+1일까지 계산한다. 
		//왜 n+1 일이냐면 만약 첫째날의 상담기간이 3일 걸리는 경우 
		//4일째되는 날에 첫째날의 결과가 저장되기 때문이다.
		for( int i=1; i<=n+1; i++ ) {
			dp[i] = Math.max( dp[i], max );
			dp[i+t[i]] = Math.max( dp[i+t[i]], dp[i]+p[i] );
			max = Math.max( max, dp[i] );
		}
		
		System.out.println( max );
	}
}

 

-자바 (dfs 이용)

package dp;

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

public class BJ14501_1 {
	static int n, ans;
	static int[][] arr;
	
	public static void dfs( int idx, int pay ) {
		if( idx >= n ) {
			ans = Math.max( ans, pay );
			return;
		}
		
		if( idx+arr[idx][0] <= n ) dfs( idx+arr[idx][0], pay+arr[idx][1] );
		else dfs( idx+arr[idx][0], pay );
		
		dfs( idx+1, pay );
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt( br.readLine() );
		StringTokenizer st;
		
		arr = new int[n][2];
		for( int i=0; i<n; i++ ) {
			st = new StringTokenizer( br.readLine() );
			arr[i][0] = Integer.parseInt( st.nextToken() );
			arr[i][1] = Integer.parseInt( st.nextToken() );
		}
		
		ans = 0;
		dfs( 0, 0 );
		
		System.out.println( ans );
	}
}

 

 

-파이썬

from sys import stdin
input = stdin.readline
n = int( input() )
arr = [ [0]*2 for _ in range( n ) ]
for i in range( n ):
    arr[i][0], arr[i][1] = map(int, input().split())
ans = 0

def dfs( idx, pay ):
    global n, ans, arr
    if idx >= n:
        ans = max( [ans, pay] )
        return
    
    if idx+arr[idx][0] <= n: dfs( idx+arr[idx][0], pay+arr[idx][1] )
    else: dfs( idx+arr[idx][0], pay )
    
    dfs( idx+1, pay )

dfs( 0, 0 )
print( ans )