Kcode

www.acmicpc.net/problem/12865

이번에 풀어본 문제는 대표적이라 하는(?) 냅색 문제이다.

냅색 문제는 가방에 무게와 가치가 주어졌을 때, 가방의 무게 안에 가장 큰 가치를 챙기게 하는 로직으로 가야한다.

그리디한 방식으로는 전부 반례가 있다.

#include <iostream>
using namespace std;

int n, k, ar[101][2], d[101][100001];

int main() {
	cin >> n >> k;
	for (int i = 1; i <= n; i++) cin >> ar[i][0] >> ar[i][1];

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= k; j++) {
			if (j < ar[i][0]) d[i][j] = d[i - 1][j];
			else d[i][j] = max(d[i - 1][j - ar[i][0]] + ar[i][1], d[i - 1][j]);
		}
	}
	//for (int i = 1; i <= n; i++) {
	//	for (int j = 0; j <= k; j++) {
	//		cout << d[i][j] << ' ';
	//	}
	//	cout << '\n';
	//}
	cout << d[n][k] << endl;

	return 0;
}

바텀업으로 풀어봤다. 주목해야 할 코드는

		if (j < ar[i][0]) d[i][j] = d[i - 1][j];
		else d[i][j] = max(d[i - 1][j - ar[i][0]] + ar[i][1], d[i - 1][j]);

이 코드다. 

이중 포문으로 j를 하나씩 올려가면서 현재 가방의 무게보다 작다면, 그 윗 단계의 가방을 가져오고,

j가 현재 가방의 무게 이상이라면 이번 가방의 가치를 포함한 것과, 포함하지 않고 전 단계의 가방을 가져온 것의 합 중 

큰 것을 가져온다.

주석 처리한 코드로 살펴보면 어떤 식으로 진행되는지를 알 수 있다. 식은 간단하지만 이해하는데는 생각보다 오래 걸린다.

#include <iostream>
using namespace std;

int n, k, ar[101][2], d[101][100001];

int go(int i, int w) {
	if (i == n + 1) return 0;
	if (d[i][w]) return d[i][w];
	int n = 0, n2;
	if (w + ar[i][0] <= k) n = ar[i][1] + go(i + 1, w + ar[i][0]);
	n2 = go(i + 1, w);
	return d[i][w] = n > n2 ? n : n2;
}

int main() {
	cin >> n >> k;
	for (int i = 1; i <= n; i++) cin >> ar[i][0] >> ar[i][1];

	cout << go(1, 0) << endl;

	return 0;
}

이번에는 무게를 함수 인자로 넘겨줘서 메모이제이션을 해줬다.

	if (w + ar[i][0] <= k) n = ar[i][1] + go(i + 1, w + ar[i][0]);
	n2 = go(i + 1, w);
	return d[i][w] = n > n2 ? n : n2;

이번 물건의 무게를 포함한 무게가 버틸 수 있는 무게를 넘지 않았다면 넣어보고, 그냥 넣지 않고 스킵한 것중 큰 값을 

dp에 넣어서 리턴해준다.

#include <iostream>
#include <algorithm>
using namespace std;

int d[100001], ar[101][2];

int main() {
	int n, k;
	cin >> n >> k;

	for (int i = 0; i < n; i++) cin >> ar[i][0] >> ar[i][1];

	for (int i = 0; i < n; i++) {
		for (int j = k - ar[i][0]; j >= 0; j--) {
			d[j + ar[i][0]] = max(ar[i][1] + d[j], d[j + ar[i][0]]);
		}
	}
	cout << d[k];

	return 0;
}

다 풀고 풀이를 확인하던 중에 어떤 분이 1차원 dp로 푸는 걸 보고 따라해봤다.

		for (int j = k - ar[i][0]; j >= 0; j--) {
			d[j + ar[i][0]] = max(ar[i][1] + d[j], d[j + ar[i][0]]);
		}

전체 k에서 가방의 무게를 빼주고 뒤에서부터 인덱스를 채우는 식이다.

i가 끝날때마다 가방 하나씩 체크하고 다시 갱신하는 식이라 시간복잡도가 훨씬 줄어듦을 예상할수 있다.

참신한 방법이라 생각했다.

냅색 문제는 dp의 대표적인 유형이라는데 비슷한 유형의 문제가 나오면 잘 풀 수 있도록 노력해봐야겠다.

방학부터 시작해서 여러 가지 문제들을 풀었지만 내가 푼 문제 수에 비해 얻은 지식량이 너무 미흡하고, 제대로 공부를 하고 있는 느낌이 들지 않아서 오답노트 겸 글을 남긴다. 

첫 번째 문제는 최근에 올라온 문제인 회의실 배정 2, 3이다.

www.acmicpc.net/problem/19621

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> ar;
int res, n;

void dfs(int cnt, int sum) {
	if (cnt > n - 1) {
		res = max(res, sum);
		return;
	}
	dfs(cnt + 1, sum);
	dfs(cnt + 2, sum + ar[cnt]);
}

int main() {
	cin >> n;
	ar.resize(n);
	for (int i = 0; i < n; i++) cin >> ar[i] >> ar[i] >> ar[i];
	dfs(0, 0);

	cout << res << endl;

	return 0;
}

회의실 배정 2는 백트래킹으로 해결했다. 

• 임의의 회의 K(1≤ K ≤ N)는 회의 K − 1과 회의 K + 1과는 회의 시간이 겹치고 다른 회의들과는 회의 시간이 겹치지 않는다.

이 조건에서 어짜피 정렬 순으로 나오고, 이번 회의에 참여했다면 그 전이나 다음 회의는 못하기에

dfs(cnt+1, sum) //이번 회의를 건너뛴다면,
dfs(cnt+2, sum + ar[cnt]) //이번 회의에 참석한다면,

이런 식으로 코드를 작성했고 

처음엔 if (cnt==n-1) 으로 작성했는데 종료 조건을 찾지 못하고 무한 루프에 빠지기에 금방 알아챘다.

www.acmicpc.net/problem/19622

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
using ll = long long;

#define X first
#define Y second

ll d[100001][2]; //n번째, 참여 1, 미참 0
vector<pair<pair<ll, ll>, ll>> ar;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	ll n;
	cin >> n;
	ar.resize(n + 1);
	for (int i = 1; i <= n; i++) cin >> ar[i].X.X >> ar[i].X.Y >> ar[i].Y;

	d[1][1] = ar[1].Y;
	d[2][1] = ar[2].Y; d[2][0] = ar[1].Y;
	for (int i = 3; i <= n; i++) {
		d[i][0] = max(d[i - 1][0], d[i - 1][1]);
		d[i][1] = d[i - 1][0] + ar[i].Y;
	}
	cout << max(d[n][0], d[n][1]) << endl;

	return 0;
}

이번엔

• 1 ≤ N ≤ 100,000

이 조건 때문에 백트래킹으론 해결할 수 없다.

d[i][0] 은 회의에 참여하지 않음

d[i][1] 은 회의에 참여함

으로 두고 점화식을 세웠다.

		d[i][0] = max(d[i - 1][0], d[i - 1][1]);
		d[i][1] = d[i - 1][0] + ar[i].Y;

이번 회의에 참여하지 않았다면, 전 회의에 참여한 것과, 참여하지 않은 것의 최댓값을 가져오고,

이번 회의에 참여했다면, 전 회의에는 참여하지 못하니 d[i-1][0] 에 현재 값을 더해준다.

이친 수 문제와 비슷한 것 같다.