[백준] 2011번: 암호코드

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

문제

예제, 반례

0
> 0

011 
> 0

0101 
> 0

1203 
> 1

2626 
> 4

2727
> 1

1
> 1

9
> 1

10
> 1

20
> 1

11
> 2

26
> 2

27
> 1

30
> 0

01
> 0

99
> 1

100
> 0

123
> 3

101
> 1

110
> 1

103
> 1

000
> 0

007
> 0

1010
> 1

1012
> 2

2220
> 2

2626
> 4

123456789
> 3

9876543210
> 1

알고리즘 접근 방법

DP를 이용한다.

나올 수 있는 해석의 가짓수를 1000000으로 나눈 나머지 배열 dp가 있다.

N자리 수 일때 왼쪽부터 한 숫자(i=1~N)씩 본다.

0. 제일 중요한 예외 ! 코드 맨 앞자리가 0이면 그냥 0이다.

if (num[1] == 0)
	dp[N] = 0

1. 초기식 설정

후에 dp[2] 를 위해 : dp[0] = 1
1~9 : dp[1] = 1

2. 현재 숫자가 0인지 아닌지 본다.
1) 0일 경우

• 앞자리 숫자와 합쳐서 10, 20 이면
  dp[i] = dp[i-2];
  ex. 110
  i=1 : 1 -> dp[1] = 1
  i=2 : i=0에서 파생 : (11) / i=1에서 파생 : (1,1) -> dp[2] = 1+1 = 2
  i=3 : i=1에서 파생 : (1,10) / i=2에서 파생 : (11,0) (1,1,0) -> dp[3] = 1

• 아니면 0
  dp[i] = 0;
  ex. 130
  i=1 : 1 -> dp[1] = 1
  i=2 : i=0에서 파생 : (13) / i=1에서 파생 : (1,3) -> dp[2] = 1+1 = 2
  i=3 : i=1에서 파생 : (1,30) / i=2에서 파생 : (13,0) (1,3,0) -> dp[3] = 0

2) 0이 아닐 경우

• 26이하고 0_ 이 아니면 (11~19, 21~26)
  dp[i] = dp[i-1] + dp[i-2];
  ex. 117
  i=1 : 1 -> dp[1] = 1
  i=2 : i=0에서 파생 : (11) / i=1에서 파생 : (1,1) -> dp[2] = 1+1 = 2
  i=3 : i=1에서 파생 : (1,17) -> dp[3] / i=2에서 파생 : (11,7) (1,1,7) = 1+2 = 3

• 그 외
  dp[i] = dp[i-1];

  • 26이상일 경우
    ex. 127
    i=1 : 1 -> dp[1] = 1
    i=2 : i=0에서 파생 : (12) / i=1에서 파생 : (1,2) -> dp[2] = 1+1 = 2
    i=3 : i=1에서 파생 : (1,27) / i=2에서 파생 : (12,7) (1,2,7) -> dp[3] = 2
  • 0_일 경우 ex. 103
    i=1 : 1 -> dp[1] = 1
    i=2 : i=0에서 파생 : (10), i=1에서 파생 : (1,0) -> dp[2] = 1+0 = 1
    i=3 : i=1에서 파생 : (1,03) / i=2에서 파생 : (10,3), (1,0,3) -> dp[3] = 1

3. 마지막으로 1000000으로 나눔에 유의한다.
dp[i] %= MOD

풀이

#include <iostream>
#include <string>
#include <string.h>

#define MOD 1000000

using namespace std;


int main(){

    string code;
    cin >> code;

    int length = code.length(); // 암호 길이 1~5000

    long long dp[length+1] = {0, }; //나올 수 있는 해석의 가짓수를 1000000으로 나눈 나머지
    memset(dp, 0, sizeof(dp)); // 0으로 초기화

    int num[length+1]; // 문자열 -> int 
    for (int i=0; i<length; i++)
        num[i+1] = code[i] - '0'; // 문자열 -> int 
    
    if (num[1] == 0)  // 1. 맨 앞자리가 0일 경우 -> 0
        dp[length] = 0;

    else{
        dp[0] = 1;
            // 1자리 암호일 경우
        dp[1] = 1; // 1~9 = 1
        for (int i=2; i<=length; i++){
            if (num[i] == 0){  // 2. 현재 숫자가 0일 경우 : 앞에 숫자가 1이나 2면 OK 아니면 0 
                if (num[i-1] == 1 || num[i-1] == 2) // 10, 20
                    dp[i] = dp[i-2];
                else // 30, 40, ...
                    dp[i] = 0;
            }
            else{ // 2. 현재 숫자가 0이 아닐 경우
                int a = num[i-1] * 10 + num[i] ;
                if (a<= 26 && num[i-1] != 0){  // 11~26 
                    dp[i] = dp[i-1] + dp[i-2]; 
                }

                else{
                    dp[i] = dp[i-1];
                }
            }
            
            dp[i] %= MOD;
        }
    }
    cout << dp[length] << endl;
    

    return 0;
}

정리

진짜 나를 화나게 했던 문제
점화식은 맞게 풀었는데 0때문에 고통 많이 받았다..
예외처리를 잘 합시다 ..^^

💡 참고 포스팅

풀면서 시도한 반례들 올립니다
혹시 반례 못찾으시겠는분
게임이 더 좋아님 블로그