[백준 2011번] - 암호코드 (C/C++)

2011번: 암호코드

[문제 설명]

---

[문제 풀이]

조건을 잘못 적용해서 엄청 틀렸다..

문제를 푼 방식은 아래와 같다.

길이에 따라 암호 해석 가짓수를 저장할 배열 dp를 선언한다. 

 

1. 앞에서부터 차례로 문자를 확인한다.

2. 현재 문자가 '0'인지를 확인한다.

2-1. 문자가 '0'이 아니라면 dp[i+1] += dp[i] ( 1(A) -> 11(AA)의 경우)

3. 이 전 문자가 '1'이거나 '2'이면서 현재 문자가 '0' ~ '6' 사이라면 dp[i+1] += dp[i-1] ( 0 -> 11(K)의 경우)

4. '0'이 연속으로 두번 나오는 경우는 암호가 잘못되었다고 생각할 수 있으므로 '0'을 출력한다.

5. 문자열을 모두 확인했다면 dp[len]을 출력한다.

 

dp[i+1]에 dp[i]를 넣어주는 이유는 string은 인덱스가 0부터 시작하고, dp의 인덱스는 문자의 길이를 의미하기 때문이다.

str[0]일때 우리는 길이가 1일때를 dp에 넣어야하므로 dp[0+1]을 해주어야 한다.

 

ex) 입력이 112인 경우,

2-1번의 경우 이전 문자까지의 경우의수(dp[i])를 더해주는 의미이고,

(11(AA), (K) -> 112(AAB), (KB))

3번의 경우 10~26까지 새로운 문자로 해석될수 있기 때문에 전전 문자까지의 경우의수(dp[i-1])를 더해준다.

(1(A) -> 112(AL))

따라서 총 3개가 된다.

 

파이팅 !

코드가 깨끗하고 명확하게 보일진 모르겠지만, 누군가에게 도움이 될 수도.. 있기에..

#include <bits/stdc++.h>
using namespace std;

long long dp[5001];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    string str;
    cin >> str;
    int len = str.size();
    if(str[0] == '0' || str.empty())
    {
        cout << "0\n";
        return 0;
    }
    dp[0] = 1;
    dp[1] = 1;
    for(int i = 1; i < len; i++)
    {
        if(str[i] != '0')
        {
            dp[i+1] += dp[i];
        }
        dp[i+1] = dp[i+1] % 1000000;
        if( (str[i-1] == '1') || ((str[i-1] == '2') && (str[i] >= '0' && str[i] <= '6')))
        {
            dp[i+1] += dp[i-1];
        }
        dp[i+1] = dp[i+1] % 1000000;
        if(str[i-1] == '0' && str[i] == '0')
        {
            cout << "0\n";
            return 0;
        }
    }
    cout << dp[len] << "\n";
}