[0x10] 다이나믹 프로그래밍

DP를 푸는 과정

 

1. 테이블 정의하기

2. 점화식 찾기

3. 초기값 정하기

 

코딩테스트에 나올 수준의 DP는 일단 점화식만 찾고나면 그 뒤는 초기값을 채워넣은 후에 반복문을 돌면서 배열을 채워넣으면 끝이다.

하지만 그 점화식을 찾는게 가장 어렵다.

주어진 문제가 DP로 풀 수 있는 문제라는 것 자체를 눈치채지 못할 수도 있다.

이 부분은 그저 많이 풀면서 테이블을 잡고 식을 세우는 과정을 반복학습 하는 수 밖에 없다.

 

연습 문제

 

1463: 1로 만들기

BFS로 구현할수도 있다. 하지만 DP를 이용하면 더 짧막하게 구현할 수 있다.

 

1. 테이블 정의하기

D[i] = i를 1로 만들기 위해 필요한 연산 사용 횟수의 최소값

 

2. 점화식 찾기

예를들어 D[12] 를 찾는다고 하면 총 3가지의 행동을 할 수 있다.

• 3으로 나누거나 (D[12] = D[4] + 1)
• 2로 나누거나 (D[12] = D[6] + 1)
• 1을 빼거나 (D[12] = D[11] + 1)

 

최소값을 찾는것이기 때문에 D[12] = min(D[4]+1, D[6]+1, D[11]+1)이 성립하게 된다.

즉, D[K] = min(D[K/3]+1, D[K/2]+1, D[K-1]+1) 이다.

 

3. 초기값 정의하기

D[1] = 0

 

#include <iostream>
#include <algorithm>

using namespace std;

int arr[1000001];

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	int n;
	cin >> n;

	for (int i = 2; i <= n; ++i)
	{
		arr[i] = arr[i - 1] + 1;
		if (i % 2 == 0) arr[i] = min(arr[i], arr[i / 2] + 1);
		if (i % 3 == 0) arr[i] = min(arr[i], arr[i / 3] + 1);
	}

	cout << arr[n];

	return 0;
}

 

9095: 1, 2, 3 더하기

1. 테이블 정의하기

D[i] = i를 1, 2, 3의 합으로 나타내는 방법의 수

 

2. 점화식 찾기

D[4]인 경우,

1+1+1+1, 3+1, 2+1+1, 1+2+1 / (3을 1, 2, 3의 합으로 나타내는 방법) + 1, D[3]

1+1+2, 2+2 / (2를 1, 2, 3의 합으로 나타내는 방법) + 2, D[2]

1+3 / (1을 1, 2, 3의 합으로 나타내는 방법) + 3, D[1]

D[4] = D[1] + D[2] + D[3]

D[i] = D[i-1] + D[i-2] + D[i-3]

 

3. 초기값 정의하기

D[1] = 1, D[2] = 2, D[3] = 4

초기값이 3개는 주어져야 한다.

 

#include <iostream>

using namespace std;

int arr[12];

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	int tc, n;
	cin >> tc;

	// 미리 테이블을 구해두고 바로 출력해준다
	arr[1] = 1;
	arr[2] = 2;
	arr[3] = 4;

	for (int i = 4; i <= 11; ++i)
		arr[i] = arr[i - 3] + arr[i - 2] + arr[i - 1];

	while (tc--)
	{
		cin >> n;
		cout << arr[n] << '\n';
	}

	return 0;
}

 

2579: 계단 오르기

1. 테이블 정의하기

(X) D[i] = i번째 계단까지 올라섰을 때 점수 합의 최대값 (연속해서 3개의 계단을 밟을수 없다는 조건때문에 사용할 수 없음)

(O) D[i][j] = 현재까지 j개의 계단을 연속해서 밟고 i번째 계단까지 올라섰을 때 점수 합의 최대값. i번째 계단은 반드시 밟아야 함

 

2. 점화식 찾기

• D[k][1] = max(D[k-2][1], D[k-2][2]) + S[k]
• D[k[2] = D[k-1][1] + S[k]

 

3. 초기값 정의하기

D[1][1] = S[1], D[1][2] = 0

D[2][1] = S[2], D[2][2] = S[1] + S[2]

 

#include <iostream>

using namespace std;

int arr[301];
int psum[301][3];

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	int n;
	cin >> n;

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

	psum[1][1] = arr[1];
	psum[1][2] = 0; // 현재 계단은 한개밖에 없다
	psum[2][1] = arr[2]; // 2층까지 한개를 연속해서 밟았다면 k-1개는 건너뛰었다는 뜻
	psum[2][2] = arr[1] + arr[2]; // 2층까지 두개를 연속해서 밟았다면 k-1, k 둘 다 밟았다는 뜻

	for (int i = 3; i <= n; ++i)
	{
		// i번째 계단이 연속해서 한개째 밟고 있다면 i-1번째 계단은 건너뛰고 i-2번째 계단을 밟았다는 뜻
		psum[i][1] = max(psum[i - 2][1], psum[i - 2][2]) + arr[i];
		// i번째 계단이 연속해서 두개째 밟고있는 계단이라면 i-1번째 계단을 밟았다는 뜻. 연속으로 3개는 밟지 못하므로 i-2 또는 i-1의 연속2개는 안된다
		psum[i][2] = psum[i - 1][1] + arr[i];
	}

	cout << max(psum[n][1], psum[n][2]);

	return 0;
}

 

1149: RGB거리

1. 테이블 정의하기

D[i][0] = i번째 집까지 칠할 때 비용의 최소값, i번째 집은 빨강

D[i][1] = i번째 집까지 칠할 때 비용의 최소값, i번째 집은 초록

D[i][2] = i번째 집까지 칠할 때 비용의 최소값, i번째 집은 파랑

 

2. 점화식 찾기

• D[i][0] = min(D[i-1][1], D[i-1][2]) + R[i]
• D[i][1] = min(D[i-1][0], D[i-1][2]) + G[i]
• D[i][2] = min(D[i-1][0], D[i-1][1]) + B[i]

 

3. 초기값 정의하기

D[1][0] = R[1]

D[1][1] = G[1]

D[1][2] = B[1]

 

최종적으로 D[N]중 가장 작은값을 출력하면 된다.

 

#include <iostream>
#include <algorithm>

using namespace std;

int arr[1001][3];
int r[1001], g[1001], b[1001];

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	int n, answer = 0;
	cin >> n;

	for (int i = 1; i <= n; ++i)
	{
		cin >> r[i] >> g[i] >> b[i];
	}

	arr[1][0] = r[1];
	arr[1][1] = g[1];
	arr[1][2] = b[1];

	for (int i = 2; i <= n; ++i)
	{
		arr[i][0] = min(arr[i-1][1], arr[i-1][2]) + r[i];
		arr[i][1] = min(arr[i-1][0], arr[i-1][2]) + g[i];
		arr[i][2] = min(arr[i-1][0], arr[i-1][1]) + b[i];
	}

	cout << *min_element(arr[n], arr[n]+3);

	return 0;
}

 

11726: 2×n 타일링

1. 테이블 정의하기

D[i] = 2×i 크기의 직사각형을 채우는 방법의 수

 

2. 점화식 찾기

• 2×1 크기의 타일을 하나 놓았을 때 나머지 타일을 채우는 방법의 수는 D[i-1]
• 1×2 크기의 타일을 하나 놓았을 때, 아래쪽 공간에는 똑같은 1×2 타일만 들어갈 수 있다. 이 때, 나머지 타일을 채우는 방법의 수는 D[i-2]

D[i] = D[i-1] + D[i-2]

 

3. 초기값 정의하기

D[1] = 1, D[2] = 2

 

#include <iostream>

using namespace std;

int arr[1001];
int mod = 10007;

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	int n;
	cin >> n;

	arr[1] = 1;
	arr[2] = 2;

	for (int i = 3; i <= n; ++i)
		arr[i] = (arr[i - 1] + arr[i - 2]) % mod; // 매번 mod의 나머지값만 가져가면 된다

	cout << arr[n];

	return 0;
}

 

11659: 구간 합 구하기 4

1. 테이블 정의하기

D[i] = A[1] + A[2] + ... + A[i] = D[i-1] + A[i]

 

2. 점화식 찾기

• D[j] - D[i-1] = (A[1] + A[2] + .. A[j]) - (A[1] + A[2] + .. + A[i-1)

 

3. 초기값 정의하기

D[0] = 0

 

#include <iostream>

using namespace std;

int arr[100001];
int prefixSum[100001];

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	int n, m;
	cin >> n >> m;

	for (int i = 1; i <= n; ++i)
	{
		cin >> arr[i];
		prefixSum[i] = prefixSum[i - 1] + arr[i];
	}

	while (m--)
	{
		int i, j;
		cin >> i >> j;
		cout << prefixSum[j] - prefixSum[i - 1] << '\n';
	}

	return 0;
}

 

 

기본 문제

 

1003: 피보나치 함수

#include <bits/stdc++.h>
using namespace std;

vector<pair<int, int>>v(41);

int main(void)
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	int tc;
	cin >> tc;
	v[0] = { 1, 0 };
	v[1] = { 0, 1 };
	for (int i = 2; i <= 40; ++i)
		v[i] = { v[i - 1].first + v[i - 2].first, v[i - 1].second + v[i - 2].second };
	while (tc--)
	{
		int n;
		cin >> n;
		cout << v[n].first << ' ' << v[n].second << '\n';
	}

	return 0;
}

 

1932: 정수 삼각형

#include <bits/stdc++.h>
using namespace std;

int t[501][501];
int n;

int main(void)
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

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

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

 

비재귀 top-down으로 깔끔하게 구현이 됨

처음에는 bottom-down으로 하려다가 도무지 답이 안나와서 구글링의 도움을 받았다

 

11727: 2×n 타일링 2

#include <bits/stdc++.h>
using namespace std;

int n, mod = 10007;
int t[1001];

int main(void)
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n;
	
	t[1] = 1;
	t[2] = 3;
	for (int i = 3; i <= n; ++i)
		t[i] = (t[i - 1] + t[i - 2] * 2) % mod;
	cout << t[n];

	return 0;
}

 

2193: 이친수

using namespace std;
using ll = long long;
int n;
ll t[91];

int main(void)
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

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

	return 0;
}

 

나름 자력으로 풀었음

 

1912: 연속합

#include <bits/stdc++.h>
using namespace std;
int n, mx, ans;
int t[100001];

int main(void)
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n;
	for (int i = 0; i < n; ++i) cin >> t[i];

	mx = ans = t[0];
	for (int i = 1; i < n; ++i)
	{
		mx = max(t[i], t[i] + mx);
		ans = max(ans, mx);
	}
	cout << ans;
	return 0;
}

 

절반정도는 접근했다가 생각의 늪에 빠져서 못풀고 구글링했음

최대값들 중의 최대값을 선별해야됨