[C++] 백준 2193 - 이친수 (DP)

백준 2193번 이친수 문제는 여러 가지 알고리즘 중 다이내믹 프로그래밍(dp)을 사용해서 해결하는 문제이다. 규칙(점화식)을 찾으면 코드 자체는 구현하기 간단하나 규칙을 찾지 못하면 한없이 어려운 문제 유형이다. 

문제 링크

2193번: 이친수 (acmicpc.net)

2193번: 이친수

 

알고리즘

// 1
// 10
// 100 101 
// 1000 1010 1001
// 10000 10100 10010 10001  10101

1. 이친수는 0으로 시작하지 않고 1이 두 번 이상 연속되지 않는 이진수 수이다.
2. n=5일 때까지 쭉 나열해 보았을 때 규칙이 보이는데, n=5일 때 수들은 n=4일 때 숫자들 뒤에 0만 붙인거 + n=3일 때 숫자들뒤에 01만 붙인 것이다.
3. 쉽게 말하자면 끝이 0으로 끝나는 수를 만들려면, 전단계 수에다가 0만 붙이면 전혀 규칙에 어긋날 일이 없다. +dp[i-1] 이 되고
4. 끝이 1로 끝나는 수를 만드려면 1 앞은 무조건 0이 와야 하므로(1이 두 개 이상 연속되면 안 됨) dp [i-2]에 끝에 01만 붙여주면 모든 경우의 수가 되는 것이다.
5. 마지막에 n이 90 이하이므로 무조건 int 범위를 벗어나기 때문에 long long int로 고쳐주는 것까지 생각해주자! 

 

코드

#include <iostream>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    long long int dp[91];
    dp[1]=1;
    dp[2]=1;
    dp[3]=2;
    cin>>n;
    for(int i=3;i<=n;i++){
        dp[i]=dp[i-1]+dp[i-2];
    }
    cout<<dp[n]<<'\n';

    return 0;
}

 

제출 결과

시간 넉넉하게 맞아버린 모습~