[ 백준 ] 14501번 : 퇴사

• 문제

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

14501번: 퇴사

---

• 풀이법 ( 알고리즘 )

재귀적으로 푼다.

---

• 풀이 - C++ ( C )

#include <iostream>
#include <algorithm>

using namespace std;

int n, ans; // n :백준이의 남은 상담 일수 , ans : 답
int T[16], P[16]; // T[x] : x일에 잡혀있는 상담의 기간 , P[x] : x일에 잡혀있는 상담의 비용

void solution(int startday, int sum)
{
	if (startday > n) return; // 현재 상담을 시작하는 날짜가 백준이의 퇴사일보다 크다면 

	ans = max(ans, sum); 

	for (int i = startday; i < n; i++)
		solution(i + T[i], sum + P[i]); // 시작일을 바꿔가며 체크
}

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	//input
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> T[i] >> P[i];
	}

	//solve
	solution(0, 0);


	//output
	cout << ans;
	return 0;
}

• 풀이 - JAVA

import java.util.*;

public class Main {
    public static int n, ans=0;
    public static int[] T = new int[16];
    public static int[] P = new int[16];
    
    public static void main(String args[]) {
         Scanner sc = new Scanner(System.in);
         n = sc.nextInt();
        
        for(int i = 0; i < n; i++)
        {
            T[i] = sc.nextInt();
            P[i] = sc.nextInt();
        }
        
        solution(0,0);
        
         System.out.println(ans);
    }
    
    public static void solution(int startday, int sum) 
    {
        if(startday > n) return;
        ans = Math.max(ans, sum);
        
        for(int i = startday; i < n; i++)
            solution(i + T[i], sum + P[i]);
    }
}

• 풀이 - PYTHON - dp 활용

n = int(input())
T = [0 for i in range(n+1)]
P = [0 for i in range(n+1)]
for i in range(n):
    a,b = map(int, input().split())
    T[i] = a
    P[i] = b

dp =[0 for i in range(n+1)]

for i in range(len(T)-2, -1, -1):      
    if T[i]+i <= n:       
        dp[i] = max(P[i] + dp[i + T[i]], dp[i+1])   
    else:               
        dp[i] = dp[i+1]
print(dp[0])