boj >> 2193 이친수

#include <iostream>
 
using namespace std;
// 라이의 블로그 DP #2
#define MAX 100
#define LL long long
 
LL dp[MAX][2]={0};
 
void binary(int N){
    if(N<2){
        dp[0][0] = 0;
        dp[1][0] = 0;
        dp[1][1] = 1;
    } else{
        binary(N-1);
        dp[N][0] = dp[N-1][0]+dp[N-1][1];
        dp[N][1] = dp[N-1][0];
    }
}
int main(){
    // 거꾸로 생각을 해서 dp[K][0]: K자리 이친수가 0으로 끝날 경우의 수는 K-1자리가 0으로 끝나는 경우와 K-1이 1로 끝나는 경우 합친거
    // Long long 써주기!!
    int N;
    cin >> N;
    binary(N);
    cout << dp[N][0]+dp[N][1] << endl;
}

 

1. 0으로 끝날 경우엔 뒤에 0과 1이 올 수 있다.

2. 1로 끝날 경우엔 뒤에 0밖에 오지 못한다.

 

이 두가지의 원리를 발견하고, dp의 장점인 미리 구해놓은 값을 효율적으로 재사용을 할 줄 안다면 풀 수 있는 문제였다.

처음에 이 문제를 접근할 때, 엄청 구질구질(?)하게 dp를 사용해서 메모리 오류가 계속 떴다.

하지만 이 두가지의 원리를 거꾸로 생각해보자. 내가 구해야 하는 N번째 경우의 수는 0으로 끝나는 애들이랑 1로 끝나는 애들로 나뉠 수 있다. 0으로 끝나는 애들은 바로 이전의 애가 0으로 끝나거나 1로 끝난 경우를 합한 경우의 수고, 1로 끝나는 애들은 이전의 애가 0으로 끝난 경우의 수랑 똑같다. 그리고 마지막에 이 둘을 합쳐주기만 하면 된다.

그래서 dp[MAX][2]를 만들어주고, dp[N][0]엔 N번째 이친수가 0으로 끝나는 경우의 수, 즉 N-1번째 이친수가 0으로 끝나는 경우와 1로 끝나는 경우를 합쳐서 넣어주면 된다.

그리고 dp[N][1]엔 N번째 이친수가 1로 끝나는 경우의 수, 즉 N-1번째 이친수가 0으로 끝나는 경우를 넣어주면 된다.