[알고리즘 문제] 백준2193 - 이친수

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

2193번: 이친수

 

이친수의 조건은 다음과 같다.

 

1. 이친수는 0으로 시작하지 않는다.

2. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.

 

이렇게 생각해보면, 숫자의 가장 앞쪽은 "10"이 와야한다. 그리고 문제를 풀다가 찾은 부분은에 마지막 숫자가 0이면 뒤에 0,1 아무거나 올 수 있고, 1이면 무조건 0만 올 수 있다.

 

 ※ 문제 설명을 하기 전에...[1,2,3,4]로 천의 자리가1인(한 자리가 고정된) 순열의 개수는 (4-1)! 입니다. 한 자리를 고정해놓고 남은 3개의 숫자로 순열을 만드는 경우의 수죠. 이 방법으로 이친수 문제를 푸는데 접근합니다. 

 

문제에서는 dp[]를 사용하는데, dp[5] = 3이란, 길이가5인 이천수의 개수는 3이 있다는 의미 입니다. 중요한 것은 dp[n]은 길이가 n인 이천수의 개수를 의미합니다. 그렇다면 다시 위에서 마지막 숫자가 0,1인 경우를 알아 봅시다

 

1. 길이가 n일 때 마지막 숫자가 0인 경우

마지막 숫자가 0인 경우 (n-1)의 숫자가 0,1 상관이 없기 때문에 다 올 수 있다, 이말은 즉 마지막 자리가 0으로 고정되어 있다는 의미이다(위의 순열 예에서 한 자리가 고정 된 경우) -> dp[n-1]을 더한다.

 

2. 길이가 n일 때 마지막 숫자가 1인 경우

마지막 숫자가 1인 경우일 때, n-1에 올 수 있는 숫자는 0만 올 수 있다. 이는 곧 마지막 두자리가 "01"로 고정된 경우이다 -> dp[n-2]를 더한다.

 

따라서 점화식은 = dp[n] = dp[n-1] + dp[n-2]인 경우이다. 이를 풀어서 설명하면, n자리의 이친수의 개수는 숫자의 맨 마지막이 0이거나, 01경우만 해당한다.

 

사실 이 문제는 각각의 경우의 수를 계산하면 어떠한 규칙을 찾을 수 있다(피보나치수열). 제출할 때 중요한 점은 입력값으로 90을 넣으면 이상한 값이 나온다. 아마 오버플로일 듯 한데, 배열을 선언할 때 long long으로 해주면 된다.

 

#include <iostream>

using namespace std;

int main()
{

    int n;
    cin >> n;

    long long dp[91] = {0};

    dp[1] = 1;
    dp[2] = 1;

    for (int i = 3; i <= n; i++)
    {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    cout << dp[n];
    return 0;
}