[BOJ] 2011. 암호코드(DP)

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

주어진 예제를 뜯어보자..!

25114 가 입력되었다.

DP[N]은 N까지 주어졌을 때, 나올 수 있는 암호의 해석 가짓수이다.

먼저, 

N = 0 일 때, 암호를 해석할 수 없으므로 0을 출력한다.

하지만! 점화식에 적용하기 위해 1을 저장해둘 것이다. (참고참고)

N = 1 일 때, 무조건 경우의 수는 1일 것이다.

2로 만들 수 있는 암호는 'B' 뿐이다.

N = 2 일 때, 

만들 수 있는 암호는, 'BE', 'Y' 두 가지이다.

DP[1]에서 'E'가 추가된 경우와 

DP[0]에서 Y가 추가된 경우이다.

N = 3 일 때,

만들 수 있는 암호는 'BEA', YA' 두 가지이다.

DP[2]에서 'A'가 추가된 경우이다.

DP[1]에서는 51에 해당하는 암호가 추가되어야 하는데 암호는 26 까지이므로 적합하지 않다.

N = 4 일 때,

만들 수 있는 암호는 'BEAA', YAA', BEK', YK' 네 가지이다.

DP[3]에서 'A'가 추가된 경우와,

DP[2]에서 'K'가 추가된 경우이다.

...

여기서 보면 DP[N]을 구하기 위해서 DP[N-1]과 DP[N-2]를 참조하게 된다.

점화식은

A[N}이 0이 아니라면 (A[N]이 0이라면 암호를 만들 수 없음)

A[N] = A[N] + A[N-1]. (N-1 까지 구한 암호에 현재 암호를 추가하는 경우)

또,

A[N-1] 과 A[N] 이 26 이하라면,

A[N] += A[N] + A[N-2]. (N-2 까지 구한 암호에 이전 암호와 합친 십의자리 암호를 추가하는 경우)

이 된다.

#. Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

#include <cstdio> #include <string.h> #define mod 1000000 using namespace std;   int DP[5001]; char A[5001] = { ' ', };   int main(void) {     int i;     //freopen("input.txt", "rt", stdin);     scanf("%s", A + 1);     if (A[1] == '0') {         printf("0\n");         return 0;     }          DP[0] = DP[1] = 1;     for (i = 2; i < strlen(A); i++) {         if(A[i] != '0')             DP[i] += DP[i - 1] % mod;                  if (A[i - 1] == '1' || A[i - 1] == '2' && A[i] <= '6')             DP[i] += DP[i - 2] % mod;     }       printf("%d\n", DP[strlen(A) - 1] % mod);       return 0; } Colored by Color Scripter

cs

line 7) 문자열을 문자 배열에 저장할 때, 0번 index가 비어있으면 strlen()이 제대로 동작하지 않아서 공백을 저장해줘야 한다.

line 13) 1번 index부터 문자 배열에 저장할 것이다.

line 14) 0이 입력되면 암호를 해석할 수 없으므로 0을 출력

line 19) 직관적인 문제를 먼저 해결

line 20~26) 점화식 적용!

line 21) 암호가 0일 경우, 해석할 수 없으므로 

line 24) 일의 자리가 1일 경우 조건문은 true가 되고 더이상 뒤 조건을 보지 않는다. 

* 처음에 정수로 받고 자릿수를 구한다음에 배열을 뒤집고 난리였는데.. 문자열로 받는게 훨씬 편리했다.

#. Other Code

/*
reference : subin
*/
 
#include <stdio.h>
 
int main(void){
    int cp[5001]; // 암호
    int dp[5001]={ 0, };
    
    int i=1;
    dp[0]=1;
 
    while(scanf("%1d", cp+i)!=EOF) {
        if(cp[i]>0)
            dp[i]=dp[i-1]%1000000;
            
        if(cp[i-1]==1||(cp[i-1]==2&&cp[i]<=6)) 
            dp[i]=(dp[i]+dp[i-2])%1000000;
            
        i++;
    }
    
    printf("%d\n", dp[i-1]%1000000);
}

line 14) 참신한 방법이다. 입력이 끝날 때까지 input을 받으면서 자릿수를 생각할 필요가 없어졌다.

심지어 문자로 받지 않고 %1d 형식으로 정수 한 개씩 받으면서 편리하게 처리할 수 있게 되었다.

* %1d로 받는 것은 생각지도 못 했는데, 참신한 방법인 것 같다.