[백준 6170번] [동적 계획법] World Cup Noise

Approach

https://viyoung.tistory.com/307 문제와 근본적으로 비슷한 측면이 많다.

[백준 8394번] [동적 계획법] 약수

1이 나올 수 있는지 여부는, 이전의 숫자가 1인지 아닌지 여부와 관련이 있다.

(고등학교때 배운 수형도와 비슷한 측면으로 이해해주면 충분하다)

 

dp[i][0] : i번째 자리까지 고려했을 때 나올 수 있는 총 경우의 수 중, i번째 자리가 1이 아닌 경우

dp[i][0] : i번째 자리까지 고려했을 때 나올 수 있는 총 경우의 수 중, i번째 자리가 1인 경우

 

따라서 관계식은

dp[i][0] = dp[i - 1][0] + dp[i - 1][1] (앞의 숫자가 1인지 여부와 관련이 없으므로)

dp[i][1] = dp[i - 1][0] (앞 숫자가 무조건 1이면 안된다.)

Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;

int dp[46][2]; // 0 : 해당 i에 1이 사용되지 않음, 1 : 사용 됨

int main(void){
    fastio;
    int t;
    cin >> t;
    for(int i = 1; i <= t; i++){
        memset(dp, 0, sizeof(dp));
        int v;
        cin >> v;
        dp[0][0] = 1;
        dp[0][1] = 1;
        for(int j = 1; j < v; j++){
            dp[j][0] = dp[j - 1][0] + dp[j - 1][1];
            dp[j][1] = dp[j - 1][0];
        }

        cout << "Scenario #" << i << ":\n";
        cout << dp[v - 1][0] + dp[v - 1][1] << "\n";
        cout << "\n";
    }
}