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

https://www.acmicpc.net/problem/2011

 

문제 풀이

DP로 푼 문제이다.

 

출력에서 원하는 값을 dp배열의 값으로 설정하여,

dp[i] = i번째 숫자까지 읽을 수 있는 해석의 가짓수

로 진행했다.

 

 

예제를 통해서 문제를 풀어보자.

쉽게 123으로 예시를 들겠다.

 

 

1. dp[1]의 값은 무엇일까?

당연히 하나의 숫자만 존재하므로 해석의 가짓수도 A로 하나만 존재한다.

즉, dp[1] = 1이다.

 

 

 

2. 그럼 dp[2]는?

1과 2를 따로 구분하여 인식하거나, 12를 하나의 숫자로 인식하는 두 가지 경우가 존재한다.

 

먼저 첫 번째 경우이다.

사실 각각의 숫자를 개별로 인식한다면 가짓수는 늘어나지 않는다.

즉 dp[i] = dp[i-1]이라는 뜻이다.

이때 숫자가 하나 있을 경우 즉, dp[0]의 초깃값으로 1을 설정해줘야 뒤의 dp배열의 값들이 올바르게 나올 것이다.

 

 

그럼 두 번째 경우를 보자.

두 숫자를 하나의 문자로 해석하므로 dp[i] = dp[i-2] + dp[i]를 해줘야 한다.

이때 dp[i]도 더해주는 이유는 첫 번째 경우에서 dp[i]의 값이 변경되었기에 고려해줘야 하기 때문이다.

 

 

 

3. 각 경우의 조건

3-1) 첫 번째 경우는 숫자를 개별로 인식해야 하므로 각 숫자가 0이 되어서는 안된다.

if(num[i] >= 1 && num[i] <= 9){
    dp[i] = dp[i-1] % 1000000;
}

와 같이 조건을 설정해주자.

 

 

3-2) 두 번째 경우는 두 숫자가 10이상이면서 26이하여야 할 것이다.

그래야 알파벳 중 하나로 해석이 될 수 있기 때문이다.

따로 변수 하나를 설정하여 두 숫자를 하나로 보았을 때 값을 계산해주자.

int temp = 0;
temp = num[i-1] * 10 + num[i];
if(temp >= 10 && temp <= 26){
    dp[i] = (dp[i-2] + dp[i]) % 1000000;
}

 

 

 

주의할 점

1. 입력

하나의 긴 숫자를 입력받으므로 각 숫자로 구분해줘야 한다는 점을 인지하자.

cin>>tmp;
    int leng = tmp.length();
    for(int i = 1; i <= leng; i++){
        num[i] = tmp[i-1] - '0';
    }

 

 

2. dp[1]의 값

위에서 기술했다시피 dp[0] = 1로 설정해야한다.

dp[0] = 1;

 

 

3. 1000000으로 나눈 나머지를 출력한다.

각 dp값을 갱신할 때 1000000을 나눠주어 값이 오버플로우 되지 않도록 하자.

dp[i] = dp[i-1] % 1000000;
dp[i] = (dp[i-2] + dp[i]) % 1000000;

 

 

 

전체 코드

#include <iostream>
#include <algorithm>
using namespace std;

int dp[5005];
int num[5005];
string tmp;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin>>tmp;
    int leng = tmp.length();
    for(int i = 1; i <= leng; i++){
        num[i] = tmp[i-1] - '0';
    }

    dp[0] = 1;
    for(int i = 1; i <= leng; i++){
        if(num[i] >= 1 && num[i] <= 9){
            dp[i] = dp[i-1] % 1000000;
        }

        int temp = 0;
        temp = num[i-1] * 10 + num[i];
        if(temp >= 10 && temp <= 26){
            dp[i] = (dp[i-2] + dp[i]) % 1000000;
        }
    }

    cout<<dp[leng];
    return 0;
}

 

점화식은 매우 간단했지만, 점화식을 생각하는 것이 어려웠던 DP 문제이다.

더욱더 많이 풀어보자.