Joohee Kwon

Problem

Concept & Idea

어려운 문제는 아니었다. 우선 이차원 dp[i][j]배열의 첫번째 요소 [i]값은 n자리수를 뜻한다.
또한 두번째 요소 [j]값은 마지막 자리가 0으로 끝나는 수의 갯수, 1로 끝나는 수의 갯수 로 설정해두었다.

마지막 자리가 0으로 끝나는 수는 다음자리 수를 만들 때, 0과 1로 두 가지를 더 만들 수 있다.

반면, 마지막 자리가 1로 끝나는 수는 11의 문자열을 가질 수 없기 때문에 0만 붙여서 만들 수있다.

dp[i][0]=dp[i-1][0]+dp[i-1][1]; dp[i][1]=dp[i-1][0];

이런 점화식을 만들어낼 수 있던 간단한 문제였다.
배열을 long long 으로 설정해두어야 한다.

Code

#include <iostream>
using namespace std;
long long dp[91][2];
int main() {
    int n;
    cin>>n;
    dp[1][1]=1;
    dp[2][0]=1;
    for(int i=3; 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;
}

Fealing

처음으로 점화식을 스스로 생각해내어서 맞추었다.
물론 long long 타입의 배열을 생각해내어야 하는 것은 질문 검색을 통해 알았지만..
앞으로 디피문제를 풀때는 배열값을 long long으로 설정해놓을까 싶다..
그래도 좀만 더 열심히하면 다이나믹 프로그래밍 문제를 좀 더 잘 풀지 않을까 싶다!!

Check out this code in Victoria’s Gist. Please Comment my code in this link.