백준 온라인 저지의 2193번 이친수 문제입니다.
[링크] https://www.acmicpc.net/problem/2193
문제 조건과 설명
- 0과 1로만 이루어진 수를 이진수라고 하는데, 이친수는 다음의 성질을 만족하는 수 입니다.
- 이진수 중에서 0으로 시작하지 않고, 1이 두 번 연속으로 나타나지 않는 수
- 이 문제는 이친수(pinary number)를 찾는 문제입니다.
- 예를 들어, 1, 10, 100, 101, 1000, 1001 등이 이친수입니다.
- 하지만, 10011100, 1100101, 0101 같은 수는 조건에 어긋나므로 이친수가 아닙니다.
Input
첫째 줄에는 N(1<=N<=90) 이 주어집니다.
Output
N자리 이친수의 갯수를 출력합니다.
생각한 아이디어
다이나믹 프로그래밍 분류에 속해 있던 문제입니다. 그래서 어떤 식으로든 규칙을 찾기 위해 노력했습니다.
- 큰 부분문제를 작은 부분문제로 나누어 생각할 수 있는지?
- 규칙을 찾아 점화식으로 나타낼 수 있는지?
DP를 풀기 위해서는 맨 처음 나올 수 있는 사례부터 하나씩 늘여 가면서 규칙을 찾는 것이 용이해 보였습니다.
1자리 이친수의 갯수는 1개 입니다. (1 하나)
- 2자리 이친수의 갯수는 10 으로 1개 입니다.
- 3자리 이친수의 갯수는 100, 101으로 2개 입니다.
- 4자리 이친수의 갯수는 1000, 1001, 1010 으로 3개 입니다.
- …
이렇게 하다 보니 다음과 같은 규칙을 얻을 수 있었습니다.
3자리 이친수는, 2자리 이친수에 0 또는 1을 붙이는 형태로 만들 수 있다.
- 2자리 이친수가 10 이었는데, 끝에 0 또는 1을 붙이면 3자리 이친수가 된다.
4자리 이친수는, 3자리 이친수에 0 또는 1을 붙이는 형태로 만들 수 있다.
- 3자리 이친수 중 100의 끝에 0 또는 1을 붙이면 4자리 이친수가 된다.
- 그러나 3자리 이친수 중 101의 끝에 1을 붙이면 1이 두번 연속 나타나게 되므로 0만 붙여 1010을 만들 수 있다.
[결론] N자리 이친수의 갯수…
(1) N-1자리 이친수들 중에서 0으로 끝나는 것의 갯수 * 2 (0 또는 1을 붙이므로 2개가 늘어남)
(2) N-1자리 이친수들 중에서 1으로 끝나는 것의 갯수 * 1 (1으로 끝나는 것에는 0만 붙일 수 있으므로 1개가 늘어남)
가 됩니다.
이렇게 이전의 사례로 큰 문제를 풀 수 있는 형태가 나타났습니다.
(1)의 상황은 N자리 이친수에서 0으로 끝나는 수와 1로 끝나는 수의 갯수가 각각 1개씩 증가하는 것입니다.
다시 말하자면, 2자리 이친수인 10 이 0으로 끝나므로, 3자리 이친수는 이 10에 0을 붙이거나, 1을 붙이거나 해서 총 두 개가 늘어난다는 의미입니다. (100, 101)
즉, 2자리 이친수 중 0으로 끝나는 것의 갯수만큼, 3자리 이친수 중 0과 1로 끝나는 것의 갯수가 각각 증가합니다.
(2)의 상황은, 예를 들어 3자리 이친수 중 101 은 1로 끝나므로, 여기에서 도출할 수 있는 4자리 이친수는 101에 0을 붙인 1010 만 나올 수 있으므로 1개가 증가한다는 의미입니다.
즉, 3자리 이친수 중 1로 끝나는 것의 갯수만큼, 4자리 이친수 중 0으로 끝나는 것의 갯수가 증가합니다.
이것을 코드상에서 점화식으로 구현하기 위해 다음과 같은 식을 생각했습니다.
1
2
dp[n][0] // n자리 이친수 중 0으로 끝나는 것의 갯수
dp[n][1] // n자리 이친수 중 1로 끝나는 것의 갯수
1
2
3
4
5
6
7
if (dp[n - 1][0] >= 1) { // n-1자리 이친수 중 0으로 끝나는 것의 갯수가 1 이상이면
dp[n][0] += dp[n - 1][0]; // n자리 이친수 중 0, 1로 끝나는 것의 갯수가 그만큼 증가
dp[n][1] += dp[n - 1][0];
}
if (dp[n - 1][1] >= 1) { // n-1자리 이친수 중 1으로 끝나는 것의 갯수가 1 이상이면
dp[n][0] += dp[n - 1][1]; // n자리 이친수 중 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
26
27
#include <cstdio>
#include <iostream>
using namespace std;
long long int dp[91][2];
int main() {
int N, cnt;
scanf("%d", &N);
dp[1][0] = 0;
dp[1][1] = 1;
for (int i = 2; i <= N; i++) {
if (dp[i - 1][0] >= 1) {
dp[i][0] += dp[i - 1][0];
dp[i][1] += dp[i - 1][0];
}
if (dp[i - 1][1] >= 1) {
dp[i][0] += dp[i - 1][1];
}
}
printf("%lld", dp[N][0] + dp[N][1]);
}
[참고] N이 커질수록 그 답안이 int 값을 초과할 경우가 생기므로 long long int로 바꾸어 주었습니다.