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 으로 선언하는 것에 유의해야 한다.
