[백준 알고리즘] 2193번: 이친수 (C++)

https://www.acmicpc.net/problem/2193

문제

문제 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다.

이친수는 0으로 시작하지 않는다. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다. 예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되므로 이친수가 아니다.

N(1 ≤ N ≤ 90)이 주어졌을 때, N자리 이친수의 개수를 구하는 프로그램을 작성하시오.

입력 첫째 줄에 N이 주어진다.

출력 첫째 줄에 N자리 이친수의 개수를 출력한다.

풀이

대부분의 간단한 DP 문제, 그리고 일정한 규칙에 따라 경우의 수가 증가하는 문제는 피보나치 수열이 나타나는 경우가 많은 것 같다. 손으로 일일히 계산해보았을 때, 이번 역시도 피보나치 수열이 발견되었다. 그렇게 풀면 너무나 쉽게 풀리겠지만, 이왕 패턴 빨리 발견된거, 좀 더 적극적으로 DP 를 이용하는 방법을 생각해보기로 했다.

가능한 이진수들을 적으면서 발견한 것은, 0으로 끝나는 이진수들은 그 다음 자릿수에서 다시 한번 0으로 끝나거나, 뒤에 1을 붙이거나 두가지 선택지를 선택할 수 있다. 그리고 1로 끝나는 이진수들은 다음 자릿수에서 무조건 0으로 끝나야 한다. 따라서 0으로 끝나는 경우의 수가 몇개인지, 1로 끝나는 경우의 수가 몇개인지를 알면 다음 자릿수에서 몇개의 이진수들의 경우의 수가 있는지 예측 할 수 있을 것이다.

DP를 2차원으로 활용해서 DP[i][j]에 대해 i는 자릿수, j는 끝자리 이진수를 나타내보자. 첫 몇개를 나열해보면

DP[1][0] = 0 DP[1][1] = 1

DP[2][0] = 1 DP[2][1] = 0

DP[3][0] = 1 DP[3][1] = 1

DP[4][0] = 2 DP[4][1] = 1

이런 방식으로 늘어난다. 결국 0으로 끝난 이진수는 다음 자릿수에서 1과 0 모두에게 갯수 하나씩을 주고, 1로 끝난 이진수는 다음 자릿수에서 0에게 갯수 하나를 주는 것이다. 이 패턴을 점화식으로 세워보면

느낀점

항상 DP문제를 보면 피보나치가 되는지부터 확인하고, 그렇지 않으면 어떻게 풀어야할지 막막한 마음과 절망스러운 마음에 구글에서 다른 사람들의 코드를 보는 일이 많았다. 그리고 너무나도 단순했던 문제에 허탈함을 느끼기도 했다. 이번 문제는 정말 내가 Optimal Substructure를 발견하고, 증가하는 수열의 패턴을 스스로 깨닫고 생각했다는 점에 큰 박수를 쳐주고 싶다! 여훈아 잘했다~~

코드

#include <iostream>

using namespace std;

long long dp[91][2];

int main()
{
    int n;
    cin >> n;

    dp[1][0] = 0;
    dp[1][1] = 1;

    for (int i = 2; 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;
}