DP는 정말 문제 푸는 감각이 중요한듯.
알면 너무 쉽고, 모르면 진짜 어렵다. 많이 풀어보자.
예제 푼 것들 정리!
-
* 카드 구매하기 (mid): 주어진 카드를 최댓값으로 구매하는 경우를 구하는 문제다.
11052번: 카드 구매하기
첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000)
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
|
#include <iostream>
#include <algorithm>
using namespace std;
int p[10001];
int d[1001];
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> p[i];
d[1] = p[1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
d[i] = max(d[i], d[i - j] + p[j]);
}
}
cout << d[n] << '\n';
return 0;
}
|
cs |
=> 카드 n개를 구매할 때, 카드팩은 n개 존재하고, i번째 카드팩에는 i개의 카드가 있다. 각 카드팩의 가격은 p[i]이다.
- 20: d[i]를 카드 i개를 구매하는 최댓값으로 생각하면, d[i] = max(d[i], d[i-j] + p[j])로 표현할 수 있다.
- j번째 카드팩으로 j개를 사는 비용에 i-j개를 구매하는 최댓값을 더한 게 지금까지 구한 최댓값보다 크면 갱신 해준다.
* 카드 구매하기 2 (mid) : 이번엔 최솟값이다. 근데 단순하게 max를 min으로 바꾸기만 하면 안 된다.
16194번: 카드 구매하기 2
첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000)
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;
int p[10001];
int d[1001];
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> p[i];
for (int i = 1; i <= n; i++)
d[i] = -1;
d[1] = p[1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
if (d[i] == -1) {
d[i] = d[i - j] + p[j];
}
d[i] = min(d[i], d[i - j] + p[j]);
}
}
cout << d[n] << '\n';
return 0;
}
|
cs |
=> max를 min으로 바꾸기만 하면 d[i] 값은 죄다 0이 될거다. d 배열이 0으로 초기화 되기 때문이다.
- 16 : 계산 되지 않은 값을 구분하기 위해 d 배열을 -1로 초기화 해준다.
- 23~26 : d[i]가 -1이면 아직 계산되지 않은 값이므로, d[i]에 d[i-j] + p[j] 값을 먼저 넣어준 다음 최솟값을 판별해준다.
* 1, 2, 3 더하기 5 (high) : 앞에서 풀었던 1, 2, 3 더하기에서 같은 값을 연속해서 더하면 안 된다는 조건이 추가된 버전이다. 여기서부터는 이차원 배열을 활용하는 dp 문제가 등장하기 시작한다. 꽤 많이 헤맸다
15990번: 1, 2, 3 더하기 5
각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.
www.acmicpc.net
- d[i][j]에서 i는 현재의 값이고 j는 마지막으로 더한 수다. 1, 2, 3이 들어갈 수 있다. 이를 활용해서 점화식을 세우면,
- d[i][1] = d[i-1][2] + d[i-1][3], d[i][2] = d[i-2][1] + d[i-2][3], d[i][3] = d[i-3][1] + d[i-3][2]
=> 마지막에 1을 더 했으면, 그 전에는 2 혹은 3을 더했을 것이다. 2, 3도 같은 원리로 생각해준다.
- d[i][1] + d[i][2] + d[i][3] : i를 만들기 위해 마지막으로 1, 2, 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
34
35
36
37
38
39
40
41
42
43
44
|
#include <iostream>
const long long mod = 1000000009;
using namespace std;
long long d[100001][4];
int main()
{
for (int i = 1; i <= 100000; i++) {
if (i >= 1) {
d[i][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][3];
if (i == 2) {
d[i][2] = 1;
}
}
if (i >= 3) {
d[i][3] = d[i - 3][1] + d[i - 3][2];
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 |
* 쉬운 계단 수 (high) : 이 또한 이차원 배열로 생각해서 풀어볼 수 있다. 엄청 헤맸다 이것도..
10844번: 쉬운 계단 수
첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.
www.acmicpc.net
- d[i][j]에서 i는 현재의 값이고, j는 마지막 계단의 크기다. j는 0부터 9까지 가능한데, 0과 9는 예외 처리를 해줘야 한다.
- 0에서는 다음 계단으로 올 수 있는 게 1뿐이고, 9에서는 8뿐이다. 나머지는 +1, -1로 2개씩 올 수 있다. 또한 0은 첫번째 계단으로 올 수 없다. 이를 고려해서 점화식을 세워주면,
- j-1 >= 0 일 때, d[i][j] += d[i-1][j-1], j + 1 <= 9 일 때, d[i][j] += d[i-1][j+1]
=> j가 0일 때는 두번째 조건에만, 9일 때는 첫번째 조건에만 해당한다. 나머지 계단은 두 조건에 모두 해당된다.
- d[i][0]에서 d[i][9]까지 더한 값이 구하고자 하는 값이다.
|
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
|
#include <iostream>
using namespace std;
long long d[101][10];
const long long mod = 1000000000;
int main()
{
int n;
cin >> n;
for (int i = 1; i <= 9; i++)
d[1][i] = 1;
for (int i = 2; i <= n; i++) {
for (int j = 0; j <= 9; j++) {
d[i][j] = 0;
if (j - 1 >= 0) d[i][j] += d[i - 1][j - 1];
if (j + 1 <= 9) d[i][j] += d[i - 1][j + 1];
d[i][j] %= mod;
}
}
long long sum = 0;
for (int i = 0; i <= 9; i++)
sum += d[n][i];
cout << sum % mod << '\n';
return 0;
}
|
cs |
* 이친수(mid) : 간단한 문제라고 생각했는데 신기한 스킬이 있었다.
2193번: 이친수
0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않
www.acmicpc.net
- 0으로 시작하지 않고, 1이 반복해서 나올 수 없는 수를 이친수라고 한다. 우선 해왔던 것처럼 이차원을 사용해본다.
- d[i][j] : i는 자리수다. j는 마지막에 온 수로 0이나 1 밖에 없다. 이를 바탕으로 점화식을 세우면,
- j == 0 일 때 d[i][j] += (d[i-1][0] + d[i-1][1]), j == 1 일 때 d[i][j] += d[i-1][0]
=> 마지막에 온 수가 0이면 바로 앞에는 0, 1 다 올 수 있다. 하지만 1이면 0 밖에 못 온다.
|
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
|
#include <iostream>
using namespace std;
long long d[91][2];
int main()
{
int n;
cin >> n;
d[1][0] = 0; d[1][1] = 1;
for (int i = 2; i <= n; i++) {
for (int j = 0; j < 2; j++) {
d[i][j] = 0;
d[i][j] += d[i - 1][0];
if (j == 0) d[i][j] += d[i - 1][1];
}
}
cout << d[n][0] + d[n][1] << '\n';
return 0;
}
|
cs |
- 근데 이걸 일차원 배열로도 풀 수 있다고 한다.
- d[i]를 i자리 이친수의 개수로 생각해보자. 마지막으로 온 수가 0 혹은 1일 것이다. 0일 때는 어떤 수가 와도 상관 없으므로 d[i-1]의 값과 똑같다. 1일 때는 바로 뒤에 0밖에 못 오는데, 그 뒤에는 어떤 수가 와도 상관 없다. 따라서 d[n-2]와 같다. 결과적으로 d[n] = d[n-1] + d[n-2]라는 점화식을 얻을 수 있다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
#include <iostream>
using namespace std;
long long d[91];
int main()
{
int n;
cin >> n;
d[0] = 0;
d[1] = 1;
for (int i = 2; i <= n; i++)
d[i] = d[i - 1] + d[i - 2];
cout << d[n] << '\n';
return 0;
}
|
cs |
=> 상당히 간단해졌다. 적극 활용하자.
-
DP 부분이 생각보다 길어지고 있다. 문제 푸는 시간이 길어져서 그런 것 같다.
굳이 서두를 필요는 없지만, 정말 모르겠다면 어느정도 지난 뒤에는 요령을 파악하자.
약간 '이건 내가 풀고 만다..' 이런 마인드인 것 같은데.. 끈기는 좋지만, 배울게 아직 많다.
끙끙대는 시간보다 새로운 깨달음을 얻는 시간으로 채워보자.
잡담은 여기까지~~ 다음 문제 풀러가자~
'알고리즘 > 백준 알고리즘 강의' 카테고리의 다른 글
| 백준 알고리즘 기초 - 다이나믹 프로그래밍 (연습) (0) | 2020.07.11 |
|---|---|
| 백준 알고리즘 기초 - 다이나믹 프로그래밍 (예제2) (0) | 2020.07.09 |
| 백준 알고리즘 기초 - 다이나믹 프로그래밍 1 + 기초 예제 (0) | 2020.07.08 |
| 백준 알고리즘 기초 - 수학1 (연습) (0) | 2020.07.07 |
| 백준 알고리즘 기초 - 수학1 (0) | 2020.07.07 |
