BOJ 14501 · 퇴사

알고리즘 분류 : 브루트 포스  

재귀 함수를 이용하여 최대 수익을 구할 수 있는 문제다. 이 문제는 다이나믹 프로그래밍 방식으로도 해결할 수 있다.

• 수익 계산 종료 조건 : 날짜가 N+1 일이 된 경우 (day == N+1)
• 재귀 함수 종료 조건 : 날짜가 N+1 일을 넘은 경우 (day > N+1)
• day 번째 일에 상담을 하는 경우 : solve(day+t[day], profit+p[day])
• day 번째 일에 상담을 하지 않는 경우 : solve(day+1, profit)

C++ 소스코드

#include <cstdio>

int n, ans;
int t[16], p[16];

void solve(int day, int profit) {
    if (day == n+1) {
        if (ans < profit) ans = profit;
        return;
    }
    if (day > n+1) return;
    solve(day+t[day], profit+p[day]);
    solve(day+1, profit);
}

int main() {
    scanf("%d", &n);
    for (int i=1; i<=n; i++) scanf("%d %d", &t[i], &p[i]);
    solve(1, 0);
    printf("%d\n", ans);
    return 0;
}

Python 3 소스코드

from sys import stdin
input = stdin.readline

ans = 0
n = int(input())
t, p = [0]*(n+1), [0]*(n+1)
for i in range(1, n+1):
    t[i], p[i] = map(int, input().split())

def solve(day, profit):
    global ans
    if day == n+1:
        if ans < profit:
            ans = profit
        return
    if day > n+1:
        return
    solve(day+t[day], profit+p[day])
    solve(day+1, profit)

solve(1, 0)
print(ans)

참고

• 백준 온라인 저지 : BOJ 14501