Beakjoon 2011 암호코드

22 Feb 2021 in Algorithm

문제 링크 : https://www.acmicpc.net/problem/2011

나의 풀이

DP[i][0] = i번에서 한자리 숫자를 사용한 경우의 수
DP[i][1] = i번에서 두자리 숫자를 사용한 경우의 수
다음과 같은 한자리 수를 사용하면 {1(A) 2(B) 3(C) 4(D) 5(E) 6(F) 7(G) 8(H) 9(I)} 다음 자리에 새로운 수가 나올 수 있다. i번 자리에서 경우의 수는 i-1번째 경우의 수만큼 늘어남
DP[i][0] = DP[i][0] + DP[i-1][0]
하지만 두자리 수{10(J) 11(K) 12(L) 13(M) … 24(X), 25(Y), 26(Z)}를 사용하면 i번 자리에서 i-1의 경우의 수만큼 늘어나는 것은 동일하지만 두칸을 차지하기 때문에 다음칸의 경우의 수를 늘린다.
DP[i][1] = DP[i][1] + DP[i-1][0]
DP[i+1][0] = DP[i+1][0] + DP[i][1]

풀이 코드 : 2011 암호코드

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int DP[5000][2];
string number;

bool solution(){
    if( number[0] >= '1' && number[0] <= '9'){
        DP[0][0] = 1;
        if(number.size() >= 2){
            int num = (number[0] - '0')*10;
            num += (number[1] - '0');
            if(num >= 10 && num <= 26){
                DP[0][1]++;
                DP[1][0]++; 
            }
        }
    }
    else return false;

    for(int i=1;i<number.size();i++){
        if(number[i] >= '1' && number[i] <= '9'){
            DP[i][0] = (DP[i][0] + DP[i-1][0])%1000000;
            if(number.size() > i+1){
                int num = (number[i] - '0')*10;
                num += (number[i+1] - '0');
                if(num >= 10 && num <= 26){
                    DP[i][1] += (DP[i][1] + DP[i-1][0])%1000000;
                    DP[i+1][0] = (DP[i+1][0] + DP[i][1])%1000000; 
                }
            }
        }else if(DP[i][0] == 0){
            return false;
        }
    }

    return true;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin>>number;
    
    if(solution())
        cout<<(DP[number.size()-1][0] + DP[number.size()-1][1])%1000000<<"\n";
    else
        cout<<0<<"\n";
}

채점결과