[C++] BOJ 백준 2193 이친수

문제링크 : https://boj.kr/2193

이친수의 조건

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

2. 1이 두번 연속으로 나오지 않는다.

이 조건을 만족하려면 반드시 2자리 이상의 이친수는 10으로 시작하게 된다.

그리고 10의 뒷부분 역시 이친수의 조건을 만족해야 이친수가 될 수 있다.

DP를 이용하면 간단하게 풀린다.

5자리 이친수의 경우 아래와 같이 표현할 수 있다.

10+3자리 이친수

100+2자리 이친수

1000+1자리 이친수

10000+0자리 이친수(사실 존재하지 않음)

이를 DP 식으로 표현하면 다음과 같다.

이 식에 따라 아래와 같이 풀어주면 된다.

여기서 주의할 점은 47번째 숫자의 값이 2,971,215,073이 되어 int 표현 범위를 초과하게 된다.

반드시 long long 타입으로 선언해주어야 한다.

// BOJ 2193 이친수
#include <bits/stdc++.h>
 
using namespace std;
long long dp[91];
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // freopen("../input.txt", "r", stdin);
 
    int num;
    cin >> num;
 
    dp[0] = 1; // 0
    dp[1] = 1; // 1
    for (int i = 2; i <= num; i++)
        for (int j = 2; j <= i; j++)
            dp[i] += dp[i - j];
 
    cout << dp[num];
 
    return 0;
}

다른 사람들의 풀이 방법을 보면 피보나치 수로 풀어도 된다고 한다.

문제 접근 방법은 거의 비슷한 것으로 보인다.

// BOJ 2193 이친수
#include <bits/stdc++.h>
 
using namespace std;
long long dp[91];
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // freopen("../input.txt", "r", stdin);
 
    int num;
    cin >> num;
 
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= num; i++)
        dp[i] += dp[i - 1] + dp[i - 2];
 
    cout << dp[num];
 
    return 0;
}