[백준/C++] 알고리즘 2011번 - 암호 코드

안녕하세요! 테크지니어22입니다.

오늘은 백준 알고리즘 2011번 - 암호 코드를 풀어보도록 하겠습니다.

 

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

 

[문제 접근]

읽어보면 이전상황을 이용해 현재 상황을 구한다는 느낌이 옵니다.

즉 패턴을 발견할 수 있습니다. 동일한 구조의 작은 문제들의 해법을 이용해 동일한 구조의 큰 문제의 해법을 구할 수 있습니다.

즉 다이나믹 프로그래밍 냄새를 술술 풍깁니다.

 

[풀이 전략]

다이나믹 프로그래밍의 첫번째 단계는 점화식 정의입니다.

저는 dp[i]를 i번째까지 해석가짓수로 정의하였습니다.

왜냐구여? 일단 가장 문안하게 정의내렸습니다.

이렇게 했는데 점화식이 안구해지면 그에 맞춰서 dp[i] 정의를 다르게 하거나 dp[i][j] 정의로 변경하면 됩니다.

 

i번째 숫자과 i-1번째 숫자를 살펴보겠습니다.

(여러가지로 해석될 수 있는 이유가 한자리수인 경우와 두자리수인 경우 때문. 예를 들어 26은 'BF' 혹은 'Z'로 2가지로 해석)

 

(i-1번째 숫자 * 10 + i번째숫자) 가 10과 크거나 같고, 26보다 작거나 같은 경우

dp[i] = dp[i-2] +dp[i-1]이고

그렇지 않은 경우

dp[i] = dp[i-1]

 

잘 세운거 같죠?

그런데 이 점화식은 문제가 있습니다.

바로 '2010'과 같이 두자리수로만 해석되는 경우 반례가 있습니다.

그래서 다시 점화식을 세우면

 

i-1번째숫자가 0보다 크면 

dp[i] = dp[i-1];

 

(i-1번째 숫자 * 10 + i번째숫자) 가 10과 크거나 같고, 26보다 작거나 같은 경우

dp[i] = dp[i] +dp[i-2]

 

로 점화식을 변경할 수 있습니다.

 

두번째 단계는 점화식 초기값을 구하는 것입니다.

dp[1] = 1; // 첫번째숫자까지 해석 경우의 수

dp[0] = 1 ; // 이건 구조상 설정해둔 건데, 이렇게 하지 않으면 dp[2]를 구하는 상황의 코드를 따로 만들어줘야 합니다.

 

이제 이를 토대로 코드를 짜봅시다.

[코드]

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

typedef long long ll ;

ll dp[5001];
ll code[5001];
int main() {
  ios::sync_with_stdio(0);
    cin.tie(0); 
    string str ;
    cin >> str ;
    // dp[i] 는 i번째까지 나올 수 있는 해석 가짓수.

    // 첫자리수가 0 이면 암호해석 불가 예외 처리.
    // dp[0],dp[1] 초기화
    for(int i = 0 ; i < str.length(); i++) {
        code[i+1] = str[i] - '0';
    }
    if (code[1] == 0) { cout << 0 ; return 0;} 
    dp[0] = 1; 
    dp[1] = 1; 

    // bottom-up 방식 
    for(int i = 2 ; i <= str.length() ; i++) {
        if(code[i] != 0) { dp[i] = dp[i-1] % 1000000 ; }
        int x = code[i-1] * 10 + code[i];
        if(x >= 10 && x <= 26) dp[i] = (dp[i] + dp[i-2]) % 1000000;
    }

    cout << dp[str.length()];
    return 0 ;
}

 

[배울 점]

0-indexed, 1-indexed 헷갈리니까 유의해야 합니다.