백준 DP 문제들 3
알고리즘 기초 문제 중 DP 기본 문제(400)
비슷한 문제들인것 같아 같이 묶어서 포스팅함
1. 이친수
간단 설명
0과 1로 이루어진 수는 이진수인데, 이친수는 다음과 같은 성질을 갖는다
- 0으로 시작하지 않고
- 1이 두번 연속으로 나타나지 않는 수 -> 11을 부분 문자열로 갖지 않음
N이 주어졌을 떄, N자리 이친수의 개수를 구하는 프로그램
예시
1
2
3
4
1자리 -> 1 : 1개
2자리 -> 10, 11(X) : 1개
3자리 -> 100, 101, 110(X), 111(X) : 2개
4자리 -> 1000 1001 1010 1011(X) 1100(X) 1101(X) 1110(X) 1111(X) : 3개
점화식
dp[i][j]를 i자리수의 글자 중 j로 끝나는 수의 개수라고 하면
i는 1~90, j는 0또는 1 2가지밖에 없다
dp[i][j] 의 값은 2^N 의 값이므로, int형보다 큰 long long int를 사용함
1
2
3
4
5
6
7
8
9
dp[1][0] = 0
dp[1][1] = 1
dp[2][0] = 1
dp[2][1] = 0 (11은 불가능)
dp[3][0] = 1
dp[3][1] = 1
dp[4][0] = 2
dp[4][1] = 1
...
이런식으로 증가하게 된다
자세히 살펴보면, 0으로 끝나는 경우는 0또는 1이 올수 있지만
1로 끝나는 경우는 이후 1이 와버리면 11 부분문자열이 생성되기 때문에 0만 올 수 있다
이를 정리하면
1
2
dp[i][0] = dp[i-1][0] + dp[i-1][1]
dp[i][1] = dp[i-1][0]
으로 정리할 수 있다
소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;
int N;
long long int dp[91][2];
int main() {
cin >> N;
dp[1][1] = 1;
dp[2][0] = 1;
for (int i = 3; i <= N; i++) {
dp[i][0] = dp[i - 1][0] + dp[i - 1][1];
dp[i][1] = dp[i - 1][0];
}
cout << dp[N][0] + dp[N][1];
return 0;
}
2. 가장 긴 증가하는 부분 수열
간단 설명
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램짜기
예시
A = {10, 20, 10, 30, 20, 50} 인 경우에
가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4
점화식
dp[i]를 가장 긴 증가하는 부분수열의 길이라고 하면
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Ai 10 20 10 30 20 50
dp 1
Ai 10 20 10 30 20 50
dp 1 2
Ai 10 20 10 30 20 50
dp 1 2 1
Ai 10 20 10 30 20 50
dp 1 2 1 3
Ai 10 20 10 30 20 50
dp 1 2 1 3 2
Ai 10 20 10 30 20 50
dp 1 2 1 3 2 4
이런식으로 증가하게 된다
현재 보고있는 수 A_i가, 이전의 수 A_(i-1)보다 크다면,
가장 긴 증가하는 부분 수열을 찾고, 그 크기를 1 늘려준다 (자기도 그 수열에 포함하는것)
1
2
if a_i > a_(i-1) :
dp[i] = dp[0] ~ dp[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
31
32
33
34
35
36
37
#include <iostream>
#include <cmath>
using namespace std;
int N;
int arr[1001];
long int dp[1001];
int main() {
// freopen_s(new FILE*, "input.txt", "r", stdin);
cin >> N;
for (int i = 0; i < N; i++) {
cin >> arr[i];
dp[i] = 1;
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < i; j++) {
if (arr[i] <= arr[j]) continue;
dp[i] = max(dp[i], dp[j] + 1);
}
}
int res = 0;
for (int i = 0; i < N; i++) {
if (res < dp[i]) {
res = dp[i];
}
}
cout << res;
return 0;
}
3. 가장 긴 감소하는 부분 수열
간단 설명
가장 긴 증가하는 부분 수열 문제와는 반대로
가장 긴 감소하는 부분수열을 찾는 문제
예시
수열 A = {10, 30, 10, 20, 20, 10} 인 경우에
가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} 이고, 길이는 3
점화식
마찬가지로 dp[i]를 가장 긴 감소하는 부분 수열의 길이로 놓으면
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Ai 10 30 10 20 20 10
dp 1
Ai 10 30 10 20 20 10
dp 1 1
Ai 10 30 10 20 20 10
dp 1 1 2
Ai 10 30 10 20 20 10
dp 1 1 2 2
Ai 10 30 10 20 20 10
dp 1 1 2 2 2
Ai 10 30 10 20 20 10
dp 1 1 2 2 2 3
이런식으로 긴 부분 수열의 길이를 찾을 수 있음
1
2
if a_i < a_(i-1) :
dp[i] : dp[0]~dp[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
31
32
33
34
35
36
#include <iostream>
using namespace std;
int N;
int arr[1001];
int dp[1001];
int main() {
// freopen_s(new FILE*, "input.txt", "r", stdin);
cin >> N;
for (int i = 0; i < N; i++) {
cin >> arr[i];
dp[i] = 1;
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < i; j++) {
if (arr[i] >= arr[j]) continue;
dp[i] = max(dp[i], dp[j] + 1);
}
}
int res = 0;
for (int i = 0; i < N; i++) {
if (res < dp[i]) {
res = dp[i];
}
}
cout << res;
return 0;
}
4. 연속합
간단 설명
n개의 정수로 이루어진 임의의 수열
이 중 연속된 몇개의 수를 선택해서 구할 수 있는 합 중, 가장 큰 합을 구하는 문제
예시
10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이 주어진 경우
가장 큰 연속된 수의 합은 12, 21을 선택한 33이다
주의사항
2 -1 99인 경우 처럼 음수를 선택해도 큰 수 가 될수 있음-1, -2, -3, -4, -5처럼 원소의 값이 -1000까지 가능함
점화식
i까지 더한 수 중, 가장 큰 연속된 수의 합을 dp[i] 로 놓으면
연속된 수의 합이므로, ‘이전까지 더해온 수의 합에 자기 자신을 더한 경우’와 ‘자기 자신만 선택한 경우’를 비교한다
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
ai 10, -4, 3, 1, 5, 6, -35, 12, 21, -1
dp 10,
첫번째는 자기자신을 더한 경우만 존재
ai 10, -4, 3, 1, 5, 6, -35, 12, 21, -1
dp 10, 6
두번째는 이전까지 더해온 수(dp[0])와 자기자신(a[1])을 더한 값 6과
자기 자신만을 선택한 경우(a[1])의 값 -4를 비교한 후, 큰 값을 기록한다
ai 10, -4, 3, 1, 5, 6, -35, 12, 21, -1
dp 10, 6, 9
세번쨰도 이전까지 더해온 수와 자기자신을 더한 값 dp[1] + a[2] = 9와
자기 자신만 선택한 경우 a[2] = 3을 비교한다.
이런식으로 점화식을 뽑으면
dp[i] = max(dp[i-1] + a[i], a[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
#include <iostream>
#include <vector>
using namespace std;
int dp[100001];
int main() {
// freopen_s(new FILE*, "input.txt", "r", stdin);
int N;
cin >> N;
vector<int> v(N);
for (int i = 0; i < N; i++) {
cin >> v[i];
dp[i] = -21e8; // dp 배열의 값들을 -21억으로 초기화함
}
dp[0] = v[0]; // 첫번째 원소를 골라서 기록
for (int i = 1; i < N; i++) {
dp[i] = max(dp[i - 1] + v[i], v[i]);
}
int max = -21e8;
for (int i = 0; i < N; i++) {
if (max < dp[i]) {
max = dp[i];
}
}
cout << max;
return 0;
}
5. 제곱수의 합
간단 설명
어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다
예를 들어 11 = 3^2 + 1^2 + 1^2, 혹은 2^2 + 2^2 + 1^2 + 1^2 + 1^2로 나타날 수 있다
주어진 자연수 N을 제곱수들의 합으로 표현할 때, 그 항의 최소 개수를 구하기
11은 제곱수 세개로 구할 수 있으므로, 3이다
예시
1은 1^2 하나로 구할 수 있으므로 1
2는 1^2 + 1^2로 구할 수 있으므로 2
3도 1^2 + 1^2 + 1^2 로 구할 수 있으므로 3
4부터는 (1^2+1^2+1^2+1^2, 2^2) 중에 한가지로 구할 수 있는 방법이 있으므로 1이다
점화식
dp[i]를 N을 만드는데 필요한 제곱수의 개수라고 하면
1
2
3
4
5
6
dp[1] = 1^2 : 1
dp[2] = 1^2 + 1^2 : 2
dp[3] = 1^2 + 1^2 + 1^2 : 3
dp[4] = dp[3] + 1, 2^2 : 1
dp[5] = dp[4] + 1 : 2
...
이런식 규칙을 찾을 수 있다
5를 만드는 방법은
1^2+1^2+1^2+1^2+1^2+ vs 1을 만드는 방법에 2^2 더하기(+1) 이다
10을 만드는 방법은
1을 10번 더하는 방법 vs 6을 만드는 방법의 수 + 2^2을 더하기(+1) vs 1을 만드는 방법의 수 + 3^2를 더하기(+1)
10 vs 3 vs 2이므로 dp[10] = 2이다
점화식을 도출해보면
dp[N] = min(dp[n-1^2] + 1, dp[n-2^2] +1, dp[n-3^2] +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
41
42
#include <iostream>
#include <cmath>
using namespace std;
int N;
int dp[100001];
int main() {
cin >> N;
for (int i = 0; i <= N; i++) {
dp[i] = i; // 모두 1^2으로 만든다고 가정
}
for (int i = 1; i <= N; i++) {
// 특정 수의 제곱으로 만들 수 있는 경우에 + 1을 한 값과 비교
for (int j = 1; j * j <= i; j++) {
dp[i] = min(dp[i], dp[i - j * j] + 1);
}
}
cout << dp[N];
/*
dp[0] = 0
dp[1] = 1^2 : 1
dp[2] = 1^2 + 1^2 : 2
dp[3] = 1^2 + 1^2 + 1^2 : 3
dp[4] = dp[3] + 1, 2^2 : 1
dp[5] = dp[4] + 1 : 2
...
dp[10] = min(dp[10-1] + 1, dp[10-4] + 1, dp[10-9] + 1)
점화식
dp[N] = min(dp[n-1^2] + 1, dp[n-2^2] +1, dp[n-3^2] +1 , .... )
*/
return 0;
}
이 문제는 처음엔 소수 관련 문제인줄 알고, 소수의 dp[prime]은 모두 1인 걸 이용해서 풀었는데
시간초과가 발생했다
더 쉬운 방법이 있었다
6. 합분해
간단 설명
0~N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 문제
덧셈의 순서가 바뀐 경우는 다른 경우로 센다
또한 한 개의 수를 여러 번 쓸 수도 있다
예시
문제 설명이 너무 짧아서 예시를 그리면서 이해했다
ex1) N : 20, K = 2일 때
0~에서 20까지 정수 2개를 더해서, 그 합이 20이 되는 경우의수?
0+20, 1+19, 2+18, 3+17, … , 19+1, 20+0 총 21개
ex2) N : 6, K : 4
0 0 0 6 0 0 1 5 0 0 2 4 .. 6 0 0 0 총 84개
이런식으로 숫자들을 K개 더해서 N을 만드는 경우의 수를 구하는 문제
점화식
dp[i][j] : 정수 i개를 써서 그 합이 j가 되는 경우의 수 라고 한다면
dp[1][1] = 1개를 써서 합이 1이 되는 경우의 수는 1 하나 dp[2][1] = 2개를 써서 합이 1가 되는 경우의 수는 1+0, 0+1 2개
이런식으로 정리하면
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
i = 1인경우는 모두 1
dp[1][1] = 1
dp[1][2] = 1
dp[1][3] = 1
...
i = 2인 경우,
dp[2][1] = 2 (1+0, 0+1)
dp[2][2] = 3 (2+0, 1+1, 0+2)
dp[2][3] = 4 (3+0, 2+1, 1+2, 0+3)
dp[2][4] = 5 (4+0, 3+1, 2+2, 1+3, 0+4)
...
i = 3인 경우
dp[3][1] = 3 (1+0+0, 0+1+0, 0+0+1)
dp[3][2]
=> dp[2][0]에 2를 더한 경우, dp[2][1]에 1을 더한 경우, dp[2][2]에 0을 더한 경우의 합
= 1 + 2 + 3 = 6 ([002], [101, 011], [200 110 020])
dp[3][3] =
=> dp[2][0]에 3를 더한 경우, dp[2][1]에 2을 더한 경우, dp[2][2]에 1을 더한 경우의 합, dp[2][3]에 0을 더한 경우의 합
= 1 + 2 + 3 + 4 = 10 ([003], [102, 012], [201,111,021], [300, 210, 120, 030])
점화식 dp[i][j] = dp[0][j-1] + dp[1][j-1] + ... + dp[i][j-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>
#define MOD 1000000000
using namespace std;
int dp[201][201];
int main() {
int N, K;
cin >> N >> K;
for (int i = 0; i <= N; i++) {
dp[1][i] = 1; // 1개로 i를 만드는 수는 1개밖에 없다
}
for (int i = 1; i <= K; i++) {
for (int j = 0; j <= N; j++) {
for (int l = 0; l <= j; l++) {
dp[i][j] = (dp[i][j] + dp[i - 1][j - l]) % MOD;
// int형 overflow를 막기 위해 더하면서 나눔
}
}
}
cout << dp[K][N];
return 0;
}
특히 3중 for문 구현 부분이 많이 햇갈렸다
i는 숫자를 몇개 썼는지, j는 목표로 하는 숫자라는걸 잘 생각해보면 이해하기 쉽다