PS
[C++] 14501: 퇴사
왕방토
2022. 1. 31. 21:55
728x90
실버 Ⅲ
dfs로 푼 코드
#include <iostream>
using namespace std;
int N;
pair<int, int> sched[16];
int ans = -1;
void dfs(int day, int nooprice) {
//printf("day: %d, nooprice: %d\n", day, nooprice);
bool thereisschedule = false;
for (int i = day; i <= N; i++) {
int nextday = sched[i].first + i;
int getprice = sched[i].second;
if (nextday > N + 1) continue;
dfs(nextday, nooprice + getprice);
thereisschedule = true;
}
if (!thereisschedule) {
if (nooprice > ans) ans = nooprice;
return;
}
}
int main() {
scanf("%d", &N);
for (int i = 1; i <= N; i++) {
scanf("%d%d", &sched[i].first, &sched[i].second);
}
dfs(1, 0);
printf("%d", ans);
}
dp로 푼 코드 (결국 못 풀어서 베낌...)
#include <iostream>
#include <algorithm>
using namespace std;
pair<int, int> sched[16];
int dp[16];//0일, 1일, ... N일 까지 총 N+1개 들어가므로 16
int N;
int main() {
scanf("%d", &N);
for (int i = 1; i <= N; i++) {
scanf("%d%d", &sched[i].first, &sched[i].second);
dp[i] = sched[i].second;
}
for (int i = 1; i <= N; i++) {
int max = 0;
//i일 보다 앞의 얘들 중에
for (int j = 1; j < i; j++) {
int finday = j + sched[j].first - 1;
//끝나는 날이 i일 보다 빠르다면
if (finday < i) {
if (dp[j] > max) max = dp[j];
}
}
dp[i] += max;
}
int ans = 0;
for (int i = 1; i <= N; i++) {
int finday = i + sched[i].first - 1;
//N일 전에 끝나는 얘들에 한해서 최대값 구해주기
if (finday <= N) {
if (ans < dp[i]) ans = dp[i];
}
}
printf("%d", ans);
}
하... 우선
dfs로 푸는 건 간단했으니까 그냥 넘어가고
dp로 푸는 거.. 처음에는 knapsack 문제처럼
2차원 배열로 해서 풀 수 있지 않을까 (dp는 걍 무조건 이렇게 푸는 줄 알았음;)
했는데...! 그 모라하지
knapsack 에서 만드는 dp의 2차원 배열 중 열 부분이
선택되는 얘들 하나하나에 대응되는데
ㅋㅋㅋ 그 선택되는 얘들 사이에 dependency?라고 해야 되나 그런 게 있어서 안됐음
예를 들어서, 그냥 knapsack 문제의 경우 1번 물건을 넣었다고 해서
3번 물건을 절대 못 넣고 그런 건 없지만 (가방 용량이 허락해주면 넣음)
위의 문제에서는 (예제 1을 예시로 들면) 1일째의 일과 3일째의 일을
동시에 선택할 수가 없다. 왜냐면 1일째의 일은 (1일, 2일, 3일) 을 써야 하지만
3일째의 일도 (3일) 을 쓰기 때문에... 둘이 3일째에 각자의 price인 +10을 해줄 수 있는 건 되지만
1열에서 +10 하고 온 값이 3열에서 이어져서 +10이 되기 때문에 (dependency 고려 못해줌)
안 됨.. 안 됨!!
흑흑... 힘들었다 4시간 걸림 dp 어쩌구 하느라.......................