반응형
알고리즘 분류 : 브루트 포스
재귀 함수를 이용하여 최대 수익을 구할 수 있는 문제다. 이 문제는 다이나믹 프로그래밍 방식으로도 해결할 수 있다.
- 수익 계산 종료 조건 : 날짜가 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
반응형
이문제 파이썬 재귀로 코드를 짜봤는데요.
한가지문제가 있는데 일단 t[] p[] 길이를 n+2 보다 조금 더 줘야 될거같습니다.
왜냐하면 마지막날에도 길이 5일짜리 일이 주워질수있기떄문에 t[] 레인지를 벗어날수 있더군요.
그리고 그렇게 해도 재귀 깊이를 벗어나는 문제가 발생합니다.
찾아보니 강제로 재귀깊이를 늘려주는 기능이 있긴하던데 삼성역테 환경에서 막힌거같습니다.
이런 유형이 나오면 파이썬은 dp를 써야될거같네요