[BOJ 14501] 퇴사 (Java)

문제

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

14501번: 퇴사

 

풀이

N의 범위가 작기 때문에 완전 탐색으로 접근하였다.

상담 건을 선택 한 후, profit을 증가하여 다음 가능한 상담을 선택한다. 

상담 일수가 초과되거나 종료되었을 때의 profit의 합을 max값과 비교하여 갱신한다.

 

소스코드

package bruteforce;

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

public class BOJ14501 {
    public static int[] T, P, dp;
    public static int N;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        T = new int[N+1];
        P = new int[N+1];
        dp = new int[N+1];
        StringTokenizer st = null;
        for(int i = 1; i <= N; i++){
            st = new StringTokenizer(br.readLine());
            T[i] = Integer.parseInt(st.nextToken());
            P[i] = Integer.parseInt(st.nextToken());
        }

        for(int i = 1; i <= N; i++){
            recur(i, T[i], P[i], 0);
        }
        System.out.println(max);
    }

    public static int max = 0;
    public static void recur(int day, int time, int profit, int total){
        if(day + time >= N+1) {
            // 끝
            if(day + time == N+1){
                total += profit;
            }
            max = Math.max(max, total);
            return;
        }

        for(int i = day + time; i <= N; i++){
            recur(i, T[i], P[i], total+profit);
        }
    }
}

 

Python

DP방식

n = int(input())
t, p = [0]*n, [0]*n

for i in range(n):
    t[i], p[i] = map(int, input().split())

#dp[i]는 i일부터 마지막날까지 얻을수 있는 최대 상담 이윤

max_value = 0
dp = [0]*(n+1)
for i in range(n-1, -1, -1):
    if i + t[i] <= n:
        max_value = max(p[i] + dp[i+t[i]], max_value)
        dp[i] = max_value
    else:
        dp[i] = max_value

print(max_value)