[C++] 백준 2193번 : 이친수 (S3)

#문제

www.acmicpc.net/problem/2193

2193번: 이친수

 

#풀이 & 학습한 내용

이번 문제에서 dp배열을 int로 선언하면 "틀렸습니다"가 나온다. long long으로 dp배열을 선언하여 문제를 해결했다. 마지막에 나올 수 있는 수는 0또는 1이고 2차원 배열을 통해 N자리 이친수의 마지막 수가 0인 경우는 dp[N][0]에, 1인 경우는 dp[N][1]에 경우의 수를 저장했다. 그리고 마지막 수가 0인 경우는 바로 앞에 0,1 모두 올 수 있고, 마지막 수가 1인 경우는 바로 앞에 0만 올 수 있다는 점을 이용하여 반복문을 통해 dp배열을 채워나갔다. 이때 basis case로 dp[1][0] = 0과 dp[1][1]=1을 넣어주었다.

 

#소스코드

#include<iostream>
#include<algorithm>
 
using namespace std;
 
long long dp[91][2];
 
int main(void) {
    dp[1][0] = 0;
    dp[1][1] = 1;
 
    for (int i = 2; i <= 90; i++) {
        dp[i][0] = dp[i-1][1] + dp[i-1][0];
        dp[i][1] = dp[i-1][0];
    }
 
    int N;
    cin >> N;
    cout << dp[N][0] + dp[N][1] << '\n';
}

 

github.com/HoYoungChun/BOJ_algorithm/blob/master/Dynamic_Programming/BOJ_2193.cpp

HoYoungChun/BOJ_algorithm