[알고리즘] 혼자 못 푼 문제 정리(암호코드)

BOJ 2011 암호코드

난이도 : (백준 난이도 기준) 골5

사용 알고리즘 or 자료 구조 : 다이나믹 프로그래밍

처음 생각한 풀이

 

위와 같이 문자열을 파싱해서 다이나믹 프로그래밍을 어떻게 잘 사용하면 될 것이라고 생각했는데, 도저히 방법이 떠오르지가 않았다...

구글링 이후 풀이

숫자가 1번부터 27번 사이에 있어야 알파벳으로 해석이 가능하다.(이거는 처음부터 생각했던 거) 

 

이때 첫 숫자부터 보는데, 첫 숫자가 0이라면 잘못된 암호이므로 0을 출력하고 return 하고, 아니라면 1개를 dp 테이블에 추가한다.

 

두번째 숫자부터 1과 9 사이라면 이전 번의 dp 테이블과 암호 개수가 같으므로 더해주고, 만약 이전 숫자와 합쳤을 때 10과 26 사이에 있다면 2개 전의 dp 테이블의 암호 개수만큼 더 만들 수 있으므로 더해준다.

 

식으로 나타내면 다음과 같다.

 

if 1 <= 암호[i] <= 9    dp[i] += dp[i - 1] 

if 10 <= 암호[i - 1 ~ i] <= 26     dp[i] += dp[i - 2] 

 

위 점화식을 잘 이용하면 문제를 쉽게 풀 수 있게 된다.

 

(코드의 주석을 보면 더 이해가 갈 수 있다)

 

 

 

 

 

 

 

 

 

 

 

 

※ 스 포 주 의 ※

 

 

 

 

 

 

 

 

 

 

 

 

코드

/// BOJ 2011 암호코드

#include <iostream>

#include <vector>

#include <string>

using namespace std;

int main() {

    string str;

    cin >> str;

    vector<long long> dp(str.length() + 1, 0);

    if(str[0] == '0') {      // 암호문의 시작이 0이라면 잘못된 암호문이므로 0을 출력하고 return

        cout << 0;

        return 0;

    }

    else {

        dp[0] = 1;

        dp[1] = 1;           // 첫 문자는 0이 아니라면 해석할 수 있는 암호문의 개수가 1개임

        for(int i = 2; i < str.length() + 1; i++) {

            if(str[i - 1] >= '1' && str[i - 1] <= '9') {

                // i - 1 번째 문자가 0이 아니라면 이전 문자까지 봤을 때의 암호문의 개수와 같아짐

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

            }

            if("10" <= str.substr(i - 2, 2) && str.substr(i - 2, 2) <= "26") {

            // 만약 이전 문자와 합쳤을 때, 10이상 26이하(다른 알파벳)라면 i - 2 번째 문자까지 봤을때 만큼 개수가 늘어남

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

            }

            dp[i] %= 1000000;

        }

        cout << dp[str.length()] % 1000000;

    }

    return 0;

}

 

참고로 str[i - 1]이나 str.substr(i - 2, 2) 같이 뺄셈을 안해주려면 str 앞에 '0' 을 추가해주면 더 간단하게 풀 수 있다.