dp가 정말 풀 것 같으면서도 잘 안 풀린다.
계속 고민하다가.. 해답 보고 실소 짓고 풀고..
또 고민하다가.. 해답 보고 실소 짓고 풀고.. 반복..
감각을 키우는 것 외에는 답이 없는 것 같다.
그래도 어느정도는 감을 잡은듯 싶다.
하지만 또 뒤돌면 못 풀 것 같은 녀석이다.
푼 것들 정리 해보자
-
* 1, 2, 3 더하기 3 (low): 하던 것처럼 맨 끝을 나눠서 생각해보자
15988번: 1, 2, 3 더하기 3
각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.
www.acmicpc.net
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
#include <iostream>
using namespace std;
long long d[1000001][4];
const long long mod = 1000000009;
int main()
{
for (int i = 1; i <= 1000000; i++) {
if (i >= 1) {
d[i][1] = d[i-1][1] + d[i - 1][2] + d[i - 1][3];
if (i == 1) {
d[i][1] = 1;
}
}
if (i >= 2) {
d[i][2] = d[i-2][1] + d[i - 2][2] + d[i - 2][3];
if (i == 2) {
d[i][2] = 1;
}
}
if (i >= 3) {
d[i][3] = d[i - 3][1] + d[i - 3][2] + d[i-3][3];
if (i == 3) {
d[i][3] = 1;
}
}
d[i][1] %= mod;
d[i][2] %= mod;
d[i][3] %= mod;
}
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
cout << (d[n][1] + d[n][2] + d[n][3]) % mod << '\n';
}
return 0;
}
|
cs |
=> 1, 2, 3으로 더하는 것 외에 별다른 조건이 없으므로, 마지막에 1, 2, 3이 모두 올 수 있고 마지막 전에도 1, 2, 3이 다 올 수 있다. 크기에 따른 구별만 생각해주면 된다.
* RGB 거리 (low) : 앞의 문제처럼 맨 끝을 기준으로 생각해주면 된다.
1149번: RGB거리
첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나
www.acmicpc.net
- price[i][j]에 i번 집에 j색을 칠하는 비용을 입력한다. 색은 빨강, 초록, 파랑 밖에 없으므로 j는 0~2로 생각한다.
- d[i][j]는 i개 집을 마지막으로 j색으로 칠했을 때의 최소값으로 생각한다. 이에 따라 점화식을 세우면,
- d[i][0] = min(d[i-1][1],d[i-1[2]) + price[i][0] : 마지막에 빨강이 오면 그 전에는 초록, 파랑 밖에 못 온다. 그 중의 최솟값에 i번째에 빨강으로 칠하는 비용을 더한다. 이런 식으로 3개의 점화식을 구하고 그 중에 최솟값을 구하면 i개 집을 색칠하는 비용의 최솟값을 구할 수 있다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
#include <iostream>
#include <algorithm>
int price[1001][4];
int d[1001][4];
using namespace std;
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= 3; j++) {
cin >> price[i][j];
}
}
d[1][1] = price[1][1];
d[1][2] = price[1][2];
d[1][3] = price[1][3];
for (int i = 2; i <= n; i++) {
d[i][1] = min(d[i - 1][2], d[i - 1][3]) + price[i][1];
d[i][2] = min(d[i - 1][1], d[i - 1][3]) + price[i][2];
d[i][3] = min(d[i - 1][1], d[i - 1][2]) + price[i][3];
}
cout << min(min(d[n][1], d[n][2]), d[n][3]) << '\n';
return 0;
}
|
cs |
* 동물원 (mid) : 풀릴듯 말듯 했는데 해답을 보고 유레카를 외칠 수 밖에 없었던 문제다.
1309번: 동물원
첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다.
www.acmicpc.net
- 가로로 두칸, 세로로 n칸인 우리에 사자를 넣고자 한다. 가로로도 세로로도 붙어 있게 배치할 수는 없다고 할 때 그 경우의 수를 구하는 문제다.
- 처음에 문제를 봤을 때 사자가 몇 마리인지도 모르고 대체 어떻게 구하라는 건지 감이 안 잡혔다.
- 1마리일 때부터 경우의 수를 생각하기도 해봤지만, 별다른 규칙을 찾기도 힘들었다.
- 한참을 고민하다가 힌트를 봤다. 결국 이것도 쪼개는 거였다. dp는 결국 쪼개는 거니까...후...
- 맨 끝에 올 수 있는 경우를 생각해보자. 추가될 칸은 3가지로 생각할 수 있다. 두 칸이 모두 비어있는 경우, 왼쪽 칸이 차있는 경우, 오른쪽 칸이 차있는 경우. 그럼 조건에 따라 식을 세울 수 있다.
- d[i][j]를 i 크기인, 마지막에 j조건이 오는 경우의 수라고 생각하면 j는 위에서 말한 것처럼 3가지 경우의 수가 올 수 있다. 따라서 j는 0~2로 생각한다. 이를 바탕으로 점화식을 세우면,
- d[i][0] = d[i-1][0] + d[i-1][1] + d[i-1][2] / d[i-1][1] = d[i-1][0] + d[i-1][2] / d[i-1][2] = d[i-1][0] + d[i-1][1]
- 어떤 경우든지 비어있는 경우는 모두 포함된다. 왼쪽이 차 있을 때는 오른쪽으로, 오른쪽이 차 있을 때는 왼쪽으로 오도록 더해준다. 모든 경우를 다 더하면 가능한 배치의 수를 구할 수 있다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
#include <iostream>
using namespace std;
long long d[100001][3];
const int mod = 9901;
int main()
{
int n;
cin >> n;
d[1][0] = 1;
d[1][1] = 1;
d[1][2] = 1;
for (int i = 2; i <= n; i++) {
d[i][0] = d[i - 1][0] + d[i - 1][1] + d[i - 1][2];
d[i][1] = d[i - 1][0] + d[i - 1][2];
d[i][2] = d[i - 1][0] + d[i - 1][1];
d[i][0] %= mod;
d[i][1] %= mod;
d[i][2] %= mod;
}
cout << (d[n][0] + d[n][1] + d[n][2]) % mod << '\n';
return 0;
}
|
cs |
* 오르막 수 (mid) : lis와는 조금 다른 방법으로 생각해야 한다.
11057번: 오르막 수
오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수�
www.acmicpc.net
- 오르막 수는 수의 자리가 오름차순을 이루는 수를 말하며, 인접한 수가 같아도 오름차순으로 친다. 계속 해왔던 것처럼 마지막에 올 수 있는 경우의 수로 나눠서 생각하면 된다.
- d[i][j]를 i자리 수인, 마지막에 j가 온 경우의 수라고 생각해보자. j에 올 수 있는 건 한 자리 자연수이므로 0~9이다. 오르막 수가 되려면 i-1번째의 마지막에 온 수가 j보다 작거나 같아야 한다. 이를 통해 점화식을 구해보면,
- d[i][j] = ∑ d[i-1][k] (k <= j) : i-1자리 수에 마지막으로 k가 왔을 때, 그 k값이 j보다 작거나 같아야 오름차 수가 된다. 조건을 만족하는 경우를 모두 더해주면 d[i][j] 값을 구할 수 있다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
#include <iostream>
using namespace std;
long long d[1001][10];
const int mod = 10007;
int main()
{
int n;
cin >> n;
for (int i = 0; i < 10; i++)
d[1][i] = 1;
for (int i = 2; i <= n; i++) {
for (int j = 0; j < 10; j++) {
for (int k = 0; k <= j; k++) {
d[i][j] += d[i - 1][k];
}
d[i][j] %= mod;
}
}
long long sum = 0;
for (int i = 0; i < 10; i++)
sum += d[n][i];
cout << sum % mod << '\n';
return 0;
}
|
cs |
- 14 : 1자리 수에 마지막에 0~9가 오는 건 1개씩이다.
* 스티커 (mid) : 아까 풀었던 동물원과 비슷하게 접근하면 된다.
9465번: 스티커
문제 상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다. 상냥이가 구매한 스티
www.acmicpc.net
- 스티커를 떼면, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없을 때, 뜯을 수 있는 스티커 점수의 최댓값을 구하는 문제다. 동물원 문제에 점수를 추가했다고 생각하면 된다.
- a[i][j]를 i행 j열의 점수 (j는 위(1), 아래(2) 두가지 경우 밖에 없다) d[i][j]를 2행 i열이 j 경우일 때의 최댓값이라고 생각해보자. j 경우는 아무 것도 안 뜯을 때, 위쪽을 뜯을 때, 아래쪽을 뜯을 때로 총 3가지로 나뉜다. 따라서 j는 0~2이 온다. 이에 따라 점화식을 세우면,
- d[i][0] = max(d[i][1], d[i][2]) , d[i][1] = max(d[i][0], d[i][2]) + a[i][2] , d[i][2] = max(d[i][0], d[i][1]) + a[i][1]
- i번째에 아무 것도 뜯지 않을 때는, i-1번째 1, 2 경우 중 최댓값을 취하면 된다. 위쪽을 뜯을 때는, i-1번째에 아무 것도 안 뜯은 것과 아래쪽을 뜯은 것 중 최댓값을 구하고 거기에 a[i][2]의 점수를 더해주면 된다. 아래쪽도 똑같이 생각한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
#include <iostream>
#include <algorithm>
using namespace std;
int a[2][100001];
int d[100001][3];
int main()
{
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
for (int i = 0; i < 2; i++) {
for (int j = 1; j <= n; j++) {
cin >> a[i][j];
}
}
d[1][1] = a[0][1];
d[1][2] = a[1][1];
for (int i = 2; i <= n; i++) {
d[i][0] = max(d[i - 1][1], d[i - 1][2]);
d[i][1] = max(d[i - 1][0], d[i - 1][2]) + a[0][i];
d[i][2] = max(d[i - 1][0], d[i - 1][1]) + a[1][i];
}
cout << max(max(d[n][0], d[n][1]), d[n][2]) << '\n';
}
return 0;
}
|
cs |
* 포도주 시식 (mid) : 최대한 많은 포도주를 시식하는 경우를 구하는 문제다.
2156번: 포도주 시식
효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규
www.acmicpc.net
- 연속으로 3잔 이상은 못 마신다는 조건이 있다. 이 또한 마지막으로 마신 잔에 관심을 둔다.
- a[i]를 i번째 포도주의 양으로, d[i][j]를 i번째에 왔을 때, 연속해서 j번째 마신 경우의 최댓값이라고 생각해보자. 연속해서 3번 이상 마실 수 없기 때문에 j는 0~2라는 것을 알 수 있다. 이를 통해 점화식을 구해보면,
- d[i][0] = max(d[i-1][0], d[i-1][1], d[i-1][2]) , d[i][1] = d[i-1][0] + a[i] , d[i][2] = d[i-1][1] + a[i]
- i번째에 마시지 않는 경우는 i-1번 째에 올 수 있는 값의 최대를 구하면 된다. i번째에 연속 1번째 마시려면 i-1번째에 안 마셔야 하고 i번째에 마셔야 한다. 연속 2번째 마시려면 i-1번째에 마셔야 하고 i번째에도 마셔야 한다. 이 세 값 중의 최댓값이 포도수 시식의 최댓값이다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
#include <iostream>
#include <algorithm>
using namespace std;
int a[10001];
int d[10001][3];
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
d[1][1] = a[1];
for (int i = 2; i <= n; i++) {
d[i][0] = max(max(d[i-1][0], d[i - 1][1]), d[i - 1][2]);
d[i][1] = d[i - 1][0] + a[i];
d[i][2] = d[i - 1][1] + a[i];
}
cout << max(max(d[n][0], d[n][1]), d[n][2]) << '\n';
return 0;
}
|
cs |
* 정수 삼각형 (low) : 양쪽 끝의 예외를 잘 처리해주고 계산하면 무난하게 풀린다.
1932번: 정수 삼각형
문제 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최�
www.acmicpc.net
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
#include <iostream>
#include <algorithm>
using namespace std;
int a[501][501];
int d[501][501];
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
cin >> a[i][j];
}
}
d[1][1] = a[1][1];
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= i; j++) {
d[i][j] = max(d[i - 1][j - 1], d[i - 1][j]) + a[i][j];
if (j == 1) d[i][j] = d[i - 1][j] + a[i][j];
if (j == i) d[i][j] = d[i - 1][j - 1] + a[i][j];
}
}
int dmax = 0;
for (int i = 1; i <= n; i++) {
if (d[n][i] > dmax)
dmax = d[n][i];
}
cout << dmax << '\n';
return 0;
}
|
cs |
* 가장 큰 증가 부분 수열 (mid) : 가장 긴 증가 수열은 구해봤으니 이제 합이 가장 큰 증가 수열을 구해보자
11055번: 가장 큰 증가 부분 수열
수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수�
www.acmicpc.net
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
#include <iostream>
#include <algorithm>
using namespace std;
long long a[1001], d[1001];
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
d[i] = 1;
}
d[1] = a[1];
int dmax = a[1];
for (int i = 2; i <= n; i++) {
d[i] = a[i];
for (int j = 1; j <= i; j++) {
if (a[j] < a[i] && d[i] < d[j] + a[i]) {
d[i] = d[j] + a[i];
}
}
if (dmax < d[i]) dmax = d[i];
}
cout << dmax << ' ';
return 0;
}
|
cs |
=> 가장 긴 증가 수열을 구할 때는 1씩 더해줬다면, 가장 큰 증가 수열을 구할 때는 현재 순서의 값을 더해준다.
* 가장 긴 감소하는 부분 수열 (mid) : 같은 맥락이다. 조금만 다르게 생각해주면 된다.
11722번: 가장 긴 감소하는 부분 수열
수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} �
www.acmicpc.net
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
#include <iostream>
#include <algorithm>
using namespace std;
long long a[1001], d[1001];
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
d[i] = 1;
}
int dmin = 1;
for (int i = 1; i <= n; i++) {
d[i] = 1;
for (int j = 1; j <= i; j++) {
if (a[j] > a[i] && d[i] < d[j] + 1) {
d[i] = d[j] + 1;
}
}
if (dmin < d[i]) dmin = d[i];
}
cout << dmin << '\n';
return 0;
}
|
cs |
=> a 값을 비교할 때 부등호 순서만 반대로 바꿨다. 감소 순이니까 뒤에서부터 비교해서 구하는 방법도 있다.
* 가장 긴 바이토닉 부분 수열 (mid) : 해답을 알고 너무 어이가 없었던 문제다.
11054번: 가장 긴 바이토닉 부분 수열
첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000)
www.acmicpc.net
- 바이토닉 부분 수열은 증가했다가 감소하는 모양의 함수다. 왼쪽에서부터 증가하다가 정점을 찍고 다시 내려가는 가장 긴 수열의 길이를 구하면 된다.
- 앞에서 구현했던 증가하는 함수의 정보와 감소하는 함수의 정보를 각각 따로 구한다. 그 다음 같은 인덱스에 위치한 두 값을 더한 값에 1을 뺀 값이 최대인 것을 구하면 된다. 1을 빼주는 이유는 정점이 겹치기 때문에 하나는 빼줘야 하기 때문이다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
#include <iostream>
#include <algorithm>
using namespace std;
int a[1001], up[1001], down[1001];
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
up[i] = 1; down[i] = 1;
}
for (int i = 2; i <= n; i++) {
for (int j = 1; j < i; j++) {
if (a[j] < a[i] && up[i] < up[j] + 1)
up[i] = up[j] + 1;
}
}
for (int i = n-1; i >= 1; i--) {
for (int j = n; j > i; j--) {
if (a[j] < a[i] && down[i] < down[j] + 1)
down[i] = down[j] + 1;
}
}
int ans = 0;
for (int i = 1; i <= n; i++) {
if (up[i] + down[i] - 1 > ans)
ans = up[i] + down[i] - 1;
}
cout << ans << '\n';
return 0;
}
|
cs |
* 연속합 2 (high) : 여기서 꽤나 고생했다. 한 개의 수를 제거할 수 있다는 조건을 생각하는 게 까다로웠다.
13398번: 연속합 2
첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.
www.acmicpc.net
- 연속합은 이미 앞에서 구현한 바가 있다. 하지만 이 문제에서는 한 가지 수를 제거할 수 있다는 조건이 붙는다. 매우 작은 음수를 제거하면 연속합의 최댓값이 바뀔 수도 있는 것이다.
- a[i]에 수열의 값을 받고, d[i]에 첫번째부터 i번째까지 연속합의 최댓값을 넣어준다. 한 가지 수를 제거할 수 있다고 했기에, 만약 i번째가 제거 되었다면 첫번째부터 i-1번째까지 연속합의 최댓값과 i+1번째부터 n번째까지 연속합의 최댓값을 더한 값이 최댓값이 된다. 따라서 i번째부터 n번째까지 연속합의 최댓값을 넣어줄 d2[i]도 구해준다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
#include <iostream>
using namespace std;
int a[100001], d[100001], d2[100001];
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 1; i <= n; i++) {
d[i] = a[i];
if (d[i - 1] + a[i] > a[i])
d[i] = d[i - 1] + a[i];
}
for (int i = n; i >= 1; i--) {
d2[i] = a[i];
if (i == n) continue;
if (d2[i + 1] + a[i] > a[i]) {
d2[i] = d2[i + 1] + a[i];
}
}
int ans = d[1];
for (int i = 2; i <= n; i++) {
if (d[i] > ans)
ans = d[i];
}
for (int i = 2; i <= n - 1; i++) {
if (d[i - 1] + d2[i + 1] > ans)
ans = d[i - 1] + d2[i + 1];
}
cout << ans << '\n';
return 0;
}
|
cs |
* 타일 채우기 (high) : 타일 채우기 문제 중에서 제일 어려웠다. 맨 끝의 경우 외에 특수한 경우도 생각해줘야 풀 수 있다.
2133번: 타일 채우기
문제 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. 입력 첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다. 출력 첫째 줄에 경우의 수를 출력한다. 예제 입력 1 복사 2 예제 출력 1 복��
www.acmicpc.net
- 3*N 크기의 벽을 2*1, 1*2 크기의 타일로 채우는 경우의 수를 구하는 문제다. 2*n이면 맨 끝에 올 경우만 생각해줘도 풀 수 있는데 3이 되니까 몇 가지를 더 생각해줘야 했다.
- 우선 맨 끝에 올 수 있는 경우는 그냥 짝대기 3개가 가로로 쌓인 모양, 짝대기 하나 위에 눕혀서 두고 아래에 두개를 세운 모양, 아래에 하나 깔고 위에 두개를 세운 모양으로 총 3가지로 나뉜다. (이 정도면 거의 글로 그림을 그렸다)
- d[i]를 3*i 크기의 벽을 채우는 경우의 수라고 할 때, d[i] = 3 * d[i-2] 인 것을 알 수 있지만 여기서 끝이 아니다. 3*n 모양에서는 특수한 경우가 있다. 이건 그림이 필요할 것 같다.
- 3 * 12 를 타일로 채운 예시다. 왼쪽에서 3~6번째를 보면 위에 두 타일이 누워있고 아래에 양쪽 타일이 누운 타일을 감싸는 모양이 있다. 위 아래가 바뀐 모양을 9~12번째에서 볼 수 있다. 4칸부터 시작해서 짝수 칸에 들어갈 수 있는 특수한 모양이 2개씩 생기는 것이다. 중간에 감싸지는 누운 타일이 옆으로 추가되는 흐름으로 4, 6, 8 ... 이런 주기로 특수한 모양을 만들 수 있다. 이를 반영해서 최종 점화식을 세우면,
- d[i] = 3 * d[i-2] + ∑ 2 * d[j] ( 0<= j <= i - 4, j는 짝수) 라고 생각할 수 있다.
- 좀 뜬금 없는데, 티스토리 코드 블록 항목을 이제 발견했다... (넌 진짜 대단하다) 지금 한번 써봐야겠다.
#include <iostream>
using namespace std;
long long d[31];
int main() {
int n;
cin >> n;
d[0] = 1;
for (int i = 2; i <= n; i += 2) {
d[i] = d[i - 2] * 3;
for (int j = i - 4; j >= 0; j -= 2) {
d[i] += d[j] * 2;
}
}
cout << d[n] << '\n';
return 0;
} - 아니 이렇게 편한 방법이 있었는데 대체 뭐했냐 지금까지
- 음... 코드는 위에서 설명한 그대로다. d[0]가 1로 초기화 되어 있는데 아무 것도 없는 경우도 1개의 경우로 생각하기 위함이기도 하고 반복문을 돌리기 편하게 하기 위해서기도 하다. 직관적으로 생각하긴 좀 어려운 문제였다.
-
쓰고 보니 진짜 많은 문제를 푼 것 같다..
dp에 대해서 어느 정도 감은 잡았지만, 뭔가 dp 공부는 끝이 없을 것 같다.
주기적으로 해주지 않으면 까먹을 것 같기도 하고.. 감각을 잃지 않게 꾸준히 복습해줘야겠다.
다음은 dp의 마지막 강의인데 강의 이름이 '도전'이다. 엄청 어려운 문제가 나오려나보다.
하나라도 풀 수 있을지 도전해봐야긋다.
정리 끝!
'알고리즘 > 백준 알고리즘 강의' 카테고리의 다른 글
| 백준 알고리즘 기초 - 브루트 포스 (0) | 2020.07.15 |
|---|---|
| 백준 알고리즘 기초 - 다이나믹 프로그래밍 (도전) (0) | 2020.07.12 |
| 백준 알고리즘 기초 - 다이나믹 프로그래밍 (예제2) (0) | 2020.07.09 |
| 백준 알고리즘 기초 - 다이나믹 프로그래밍 (예제1) (0) | 2020.07.09 |
| 백준 알고리즘 기초 - 다이나믹 프로그래밍 1 + 기초 예제 (0) | 2020.07.08 |
