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 어쩌구 하느라.......................

댓글수0