백준(boj) 14501_퇴사 (파이썬, c++)

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

풀이

---

완전탐색 한다. pos가 현재 날짜이고, res가 총 이익 값이다.

base case는 pos가 n일 때 res값을 반환한다. pos가 n을 넘어가면 퇴사한 이후이므로 조건을 만족하지 못한다. 따라서 0을 반환한다.

이 문제의 경우 해당 날짜의 상담을 선택하거나 선택하지 않거나 두 가지의 경우밖에 없는데,

만약 선택을 한다면, 그 날짜에 있는 상담이 걸리는 시간을 추가해주고, 얻을 수 있는 이익도 추가해준다. (solve(pos+a[pos][0], res+a[pos][1]))

선택을 하지 않는다면, 이익은 그대로 두고 바로 다음 스케줄을 확인해주어야 한다. (solve(pos+1, res))

python3

from sys import*
input = stdin.readline
​
def solve(pos, res):
    ans = 0
    if pos > n: return 0
    if pos == n: return res
    ans = max(ans, solve(pos+a[pos][0], res+a[pos][1]), solve(pos+1, res))
    return ans
​
n=int(input())
a=[]
for i in range(n):
    a.append(list(map(int,input().split())))    #[0]날짜, [1]금액
print(solve(0,0))

C++

#include<cstdio>
#include<algorithm>
using namespace std;
int n, a[1000][2];
int solve(int pos, int res){
    int ans = 0;
    if(pos > n) return 0;
    if(pos == n) return res;
    ans = max(ans, solve(pos+a[pos][0], res+a[pos][1]));
    ans = max(ans, solve(pos+1, res));
    return ans;
}
int main(){
    scanf("%d",&n);
    for(int i=0; i<n; i++){
        scanf("%d %d", &a[i][0], &a[i][1]);
    }
    printf("%d", solve(0, 0));
    return 0;
}

고찰

---

.