[백준 2011] 암호코드 C++

2011번: 암호코드

다이나믹 프로그래밍

---

1. 문제해결 아이디어

현재 자릿수에서 어떤 암호가 만들어 질 수 있는지 dp를 이용해서 해결해야한다.

1. 우선 0은 암호로 바꿀 수 없다. 하지만 0 이전에 1 또는 2가 있다면 암호로 바뀔 수 있다.
2. 숫자 3 이상과 이어지는 암호는 없다.
3. 현재 숫자가 2인 경우 다음 숫자가 0 ~ 6 인 경우만 숫자 2개를 사용해서 암호를 만들 수 있다.

 

dp배열 : dp[i][2] -> i번 자리수 이후로 숫자를 1개 또는 2개를 사용해서 만들 수 있는 경우를 저장하는 배열.

---

2. 코드

<+36> : 2번 틀렸었는데 입력이 0으로 시작하는 경우가 있었다. 예외처리 해주니까 풀렸다.

#include <iostream>
#include <cstring>
using namespace std;
 
#define MOD 1000000
 
int N[5001];
long long dp[5001][2];
 
void solve(int n){
    dp[n-1][0] = 1;
    dp[n-1][1] = 0;
    
    for(int i = n-2; i >= 0; i--){
        dp[i][0] = (dp[i+1][0] + dp[i+1][1]) % MOD;
        dp[i][1] = dp[i+1][0];
        
        if(N[i] > 2 || (N[i] == 2 && N[i+1] > 6) || N[i] == 0){
            dp[i][1] = 0;
        }
        if(N[i+1] == 0){
            dp[i][0] = 0;
        }
    }
}
 
int main(){
    string str;
    cin >> str;
    for(int i = 0; i < str.size(); i++){
        N[i] = str[i] - '0';
    }
    
    solve(str.size());
    
    if(N[0] == 0) cout << 0;
    else cout << (dp[0][0] + dp[0][1]) % MOD;
    
    return 0;
}
 

dp가 가볍게 풀리는 그날까지ㅠ