[백준/BOJ] 2193번: 이친수 ( 동적 프로그래밍 ) - C++ 문제 풀이

문제 설명

 

문제 링크: https://www.acmicpc.net/problem/2193

 

풀이

이 문제는 숫자의 자릿수가 주어졌을 때, 만들 수 있는 이친수( pinary number )의 개수를 구하는 문제입니다.

 

적은 자릿수의 이친수로부터 더 큰 자릿수의 이친수를 만드는 과정을 생각해 보면 규칙성을 만들어 볼 수 있습니다.

 

먼저, 간단히 4 자릿수 이친수를 만든다고 해봅시다.

그럼, 3 자릿수 이친수의 끝 부분에 0을 붙이면 이친수의 규칙을 어기지 않고도 4 자릿수 이친수를 만들 수 있습니다.

 

그런데, 3 자릿수 이친수의 끝 부분에 1은 붙일 수 없습니다. 

이렇게 해서 만들어진 4 자릿수의 숫자는 이친수가 아닐 수도 있기 때문입니다. ( 예, 1011 )

 

그럼, 1로 끝나는 이친수는 만들 수 없는 걸까요?

아닙니다.

2 자릿수의 이친수에 01을 붙어도 이친수가 됩니다.

그리고, 이렇게 만든 4 자릿수 이친수는 1로 끝나는 숫자이므로, 위의 3 자릿수 이친수에 0을 붙인 숫자와 중복되지 않습니다.

 

이제, 규칙성이 보이네요.

자릿수 i를 가진 이친수를 만드는 가짓수를 f(i)라고 할 때

 

f(i) = f(i-1) + f(i-2)

의 점화식이 성립합니다.

이때, 자릿수가 1인 이친수는 1 뿐이므로, f(1) = 1입니다.

그리고, 자릿수가 0인 숫자는 없으므로 f(0) = 0.

 

이를 코드로 작성하면 다음과 같습니다.

#include <iostream>
using namespace std;

#define DIGITS    90

using mtype = long;
mtype pnum[DIGITS+1]; // 자릿수에 따른 이친수의 개수

int main(){

    int N;
    cin >> N;

    pnum[1] = 1;

    for( int i = 2; i <= N; i++){
        pnum[i] = pnum[i-1] + pnum[i-2];
    }

    cout << pnum[N];
}

 

여기서, 주의할 것은 pnum 배열의 타입을 int로 하게 되면, int의 범위를 넘어가는 경우가 발생합니다.

이럴 땐, using 키워드를 사용해서, 기존의 코드를 변경할 필요 없이, 다루고자 하는 변수의 타입을 쉽게 변경할 수 있도록 코드를 짜는 방법도 있습니다.

 

using에 관한 내용은 여기에서 볼 수 있습니다.

[C++] 별명을 만드는 typedef와 using

 

 

소스 코드

#include <iostream>
using namespace std;

#define DIGITS    90

using mtype = long;
mtype pnum[DIGITS+1]; // 자릿수에 따른 이친수의 개수

int main(){

    int N;
    cin >> N;

    pnum[1] = 1;

    for( int i = 2; i <= N; i++){
        pnum[i] = pnum[i-1] + pnum[i-2];
    }

    cout << pnum[N];
}