백준 알고리즘 기초 - 다이나믹 프로그래밍 (도전)

도저어어언

난이도가 높은 새로운 문제를 풀줄 알았는데, 기존의 문제를 좀 더 어려운 방법으로 풀거나 조건을 더 추가해서 푸는 식이었다.

새로운 문제를 푸는 것 보다 훨씬 와닿는 도전이었다. '이걸 이렇게 더 빨리 풀 수 있구나' 하는 깨달음도 얻었다.

벌써 dp 챕터의 마지막 강의다.. 정리 시작 해보자!

-

* 동물원 (high) : 2차원으로 풀던 걸 1차원으로 풀었다. 배열을 어떻게 정의하느냐가 관건이다.

1309번: 동물원

 - 기존에는 d[i][j]로 두고, i번째 줄에 j 경우일 때까지의 경우의 수로 생각했는데, 이번엔 일차원 배열로 생각해본다.

 - d[i]를 i번째에 동물이 무조건 들어가 있는 i번째까지의 경우의 수라고 생각해보자. 그럼 마지막 i번째 열에는 동물이 두 칸 중 하나에 반드시 있다는 소리다. 그럼 i-1번째에 올 수 있는 경우도 하나로 제한된다. 이미 i번째에 들어갈 곳이 정해졌기 때문에 그 반대편에 들어갔다고 생각할 수 있다. 그럼 i-2번째부터 1번째까지는 어떻게 될까? 그건 모른다. i번째와 i-1번째에 어떻게 들어갔느냐에 따라 달라진다. i번째와 i-1번째가 만들 수 있는 경우는 왼,오 / 오,왼으로 2가지다.

 - 따라서 d[i] = d[i-1] + 2 * (d[i-2] + d[i-3] + ... + d[1]) 와 같은 점화식을 얻을 수 있다. d[1]에서 d[i]까지의 합을 구하는 s[i] 배열을 따로 구하면 계산이 훨씬 편해진다.

#include <iostream>
using namespace std;

long long d[100001], s[100001];

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

	d[0] = 1; s[0] = d[0];
	d[1] = 2; s[1] = s[0] + d[1];

	for (int i = 2; i <= n; i++) {
		d[i] = (d[i - 1] + 2 * s[i - 2]) % 9901;
		s[i] = (s[i - 1] + d[i]) % 9901;
	}

	cout << s[n] % 9901 << '\n';

	return 0;
}

 

* RGB 거리 2 (high) : RGB 거리 문제에서 맨 앞과 뒤의 색깔도 달라야 하는 조건이 추가된 문제다.

17404번: RGB거리 2

 - 한마디로 집이 배열된 형태가 직선에서 맨 앞과 뒤가 인접한 원형으로 바꼈다고 생각하면 된다. '맨 앞과 맨 뒤가 달라야 하니까, 두 경우를 고정해서 최솟값을 구해야겠다'는 생각까지는 쉽게 할 수 있었는데, 방법을 생각하려니 좀 까다로웠다. 

 - 풀이를 참고하니 첫번째 값을 초기화할 때 R, G, B가 고정되도록 하고, 마지막 값을 더할 때 그 고정된 값 외에 다른 값이 더해진 최솟값을 구하도록 식을 세웠다. 이건 말보다 코드가 더 명쾌한 것 같다.

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

int a[1001][3], d[1001][3];

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

	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= 2; j++) {
			cin >> a[i][j];
		}
	}

	int ans = 1000 * 1000 + 1;
	for (int k = 0; k <= 2; k++) {
		for (int j = 0; j <= 2; j++) {
			if (j == k) d[1][j] = a[1][j];
			else d[1][j] = 1000 * 1000 + 1;

			for (int i = 2; i <= n; i++) {
				d[i][0] = min(d[i - 1][1], d[i - 1][2]) + a[i][0];
				d[i][1] = min(d[i - 1][0], d[i - 1][2]) + a[i][1];
				d[i][2] = min(d[i - 1][0], d[i - 1][1]) + a[i][2];
			}
		}

		for (int j = 0; j <= 2; j++) {
			if (j == k) continue;
			else ans = min(ans, d[n][j]);
		}
	}

	cout << ans << '\n';

	return 0;
}

 - ans는 최종값이 들어갈 곳으로, 각 항의 최댓값을 더해준 것보다 큰 수로 초기화를 해준다.

 - 그 다음 이중으로 k, j가 반복문을 도는데 이렇게 구현하면 0, 1, 2가 차례로 고정이 된다. j !=k 인 값은 큰 수로 초기화를 해준다. 그 다음 원래 해주던 것처럼 반복문을 돌려 최솟값을 구한다.

 - 최종값을 구할 때는 첫번째 항과 다른 색깔이어야 하므로 j==k일 때를 제외하고 계산한 최솟값을 구해준다.

 

* 합분해 (high) : O(N^3)으로 풀던 것을 O(N^2)으로 풀 수 있는 방법이다.

2225번: 합분해

 - 기존에는 d[k][n] = Σd[k-1][n-l] (0 <= n-l <= n) 으로 생각했는데, 조금 다르게 접근하는 방식이다.

 - 기존 점화식을 통해 n-l >= 0 인 것도 알 수 있으므로 (0<= l <= n) 조건 또한 성립한다. 따라서 n-l 자리에 l을 넣어도 식이 성립한다는 것을 알 수 있다. d[k][n] = Σd[k-1][l] (0<= l <= n) 로 식이 더 간단해졌다. 

 - 식을 풀어보면 d[k][n] = d[k-1][0] + d[k-1][1] + d[k-1][2] + ... + d[k-1][n] 이라는 것을 알 수 있고 이를 그림을 통해 나타내면,

백준님 만세

 - 보라색의 합이 파란색이 되고, 보라색과 노란색의 합이 빨간색이 되니까, 파란색 부분과 노란색의 합이 빨간색인 것을 알 수 있다. 이를 식으로 나타내면, d[k][n] = d[k][n-1] + d[k-1][n] 인 것을 알 수 있다.

#include <iostream>

using namespace std;

long long d[201][201];
const long long mod = 1000000000;

int main() {
	int n, k;
	cin >> n >> k;
	d[0][0] = 1;
	for (int i = 1; i <= k; i++) {
		for (int j = 0; j <= n; j++) {
			d[i][j] = d[i - 1][j];
			if (j - 1 >= 0) {
				d[i][j] += d[i][j - 1];
			}
			d[i][j] %= mod;
		}
	}

	cout << d[k][n] % mod << '\n';

	return 0;
}

 - 일단 바로 위에 있는 수를 더하고, j-1이 0보다 크면 왼쪽에 있는 수도 누적해서 더하면 된다.

 - 코딩 자체보다는 어떤 식으로 접근해서 문제를 나눌 것인가를 떠올리는 것이 더 중요한 것 같다.

-

이렇게 dp가 끝났다. dp까지가 이번 주 할당량이었는데, 무사히 마쳐서 기분이 좋다.

dp를 풀 때마다 느끼는 거지만 정말 '완전 정복'이 없는 것 같다. 하지만 이번 기회로 확실히 dp에 대한 감은 올라온 것 같다. 앞으로도 꾸준히 풀어봐야겠다.

이번 주도 고생했고.. 다음주도 열심히 달려보자!

백준 알고리즘 기초 1/2 정리 끝!