[백준] 2193번: 이친수

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

문제

알고리즘 접근 방법

DP를 이용한다.

끝자리가 0이면 이전에 올 수 있는 숫자는 0, 1 모두 가능하다.
끝자리가 1이면 이전에 올 수 있는 숫자는 0만 가능하다.

이를 통해 식을 세우면 다음과 같다.
dp[N][0] = dp[N-1][0] + dp[N-1][1]
dp[N][1] = dp[N-1][0];

풀이

#include <iostream>

using namespace std;

int main(){
    int N;

    cin >> N;

    long long dp[N+1][2] = {0, }; //숫자 길이와 끝자리 수 (0,1)

    dp[1][0] = 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] << endl;

    return 0;
}

정리

접근 방법은 맞았으나, 자료형에서 문제가 있었다.
이전 DP문제들과 달리 개수를 큰 수로 나누지 않고 출력하기 때문에 N이 커지면 int로 나타낼 수 있는 수의 범위를 초과한다.
따라서 타입을 long long 으로 선언하는 것에 유의해야 한다.

💡 참고 포스팅

옹구스투스님 블로그
이친수(c++) - 오답이 되는 요인이 무엇일까요?
수가 커지니까 값이 이상해집니다.