728x90
문제
https://www.acmicpc.net/problem/14501
14501번: 퇴사
첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.
www.acmicpc.net
문제해결
1. 다이나믹 문제이지만 재귀를 이용하여 풀었다.
2. 각 DAY마다 재귀를 이용하여 상담이 가능한 날짜를 탐색했다.
코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | #include <iostream> using namespace std; int N,Max = 0; int ary[16][2]; void DFS(int node,int count){ if(count >= Max){Max = count;} for(int i = node;i<=N;i++){ if(ary[i][0]+i-1>N){continue;} DFS(ary[i][0]+i,count+ary[i][1]); } return; } int main(void){ cin >> N; for(int i = 1;i<=N;i++){ cin >> ary[i][0] >> ary[i][1]; } for(int i = 1;i<=N;i++){ if(ary[i][0]+i-1>N){continue;} DFS(ary[i][0]+i,ary[i][1]); } cout << Max; } | cs |
728x90
'다이나믹 프로그래밍' 카테고리의 다른 글
[백준/C++][평범한 배낭(12865번)] (0) | 2020.12.15 |
---|---|
[백준/C++][점프 점프(11060번)] (0) | 2020.12.14 |
[백준/C++][가장 긴 감소하는 부분 수열(11722번)] (0) | 2020.12.14 |
[C++/알고리즘][다이나믹 프로그래밍(동적계획법)-DP] (2) | 2020.12.09 |
[백준/C++][가장 긴 증가하는 부분 수열(11053번)] (0) | 2020.12.03 |