#include <iostream> #include <algorithm> using namespace std; #define SIZE 16 int T[SIZE]; int P[SIZE]; int n; int maxVal; void problemIn() { cin >> n; for (int i = 1; i <= n; i++) cin >> T[i] >> P[i]; } /* 입력을 받은 다음에, 만약에 7일까지 일이 가능하다고 하면, 티를 더하고, 가격을 더하고, 어떤 조건을 만족하면, 맥스를 취합니다. 그리고 그 아래에는 인덱스만 하나 올라가고, 섬은 그대로 입니다. 오께이요. 인덱스 하나만 앞으로 올라가도록 합니다. 내가 만든 알고리즘과 비교하면 완전 차이가 많이 나네요. 뎁스는 하나 전진하고, 섬은 그대로 유지하는 것이 키워드 입니다. 그 아래와 처음 리턴하는 조건문에 대해서는 풀 수 있습니다. */ void dfs(int d, int sum) { if (d == n + 1) { maxVal = max(maxVal, sum); return; } if (d + T[d] <= n + 1) dfs(d + T[d], sum + P[d]); //d,sum 더해서 돌리기. if (d + 1 <= n + 1) dfs(d + 1, sum); } int main() { problemIn(); dfs(1, 0); cout << maxVal; return 0; } |
백준 퇴사, 디에프에스의 기본문제입니다. 이프문을 넣어서 이렇게 풀이하는 것에 익숙해지도록 합니다. 저렇게 아래에 인덱스, 깊이 하나만 이동하는 문제, 섬은 가지고 가는 문제에 대해서 알고 있도록 합니다. 섬을 가지고 갈 것인지, 배열을 가지고 갈 것 인지에 대해서 알고 있어야 합니다. 오께이. |