2011번: 암호코드

문제

상근이와 선영이가 다른 사람들이 남매간의 대화를 듣는 것을 방지하기 위해서 대화를 서로 암호화 하기로 했다. 그래서 다음과 같은 대화를 했다.

• 상근: 그냥 간단히 암호화 하자. A를 1이라고 하고, B는 2로, 그리고 Z는 26으로 하는거야.
• 선영: 그럼 안돼. 만약, "BEAN"을 암호화하면 25114가 나오는데, 이걸 다시 글자로 바꾸는 방법은 여러 가지가 있어.
• 상근: 그렇네. 25114를 다시 영어로 바꾸면, "BEAAD", "YAAD", "YAN", "YKD", "BEKD", "BEAN" 총 6가지가 나오는데, BEAN이 맞는 단어라는건 쉽게 알수 있잖아?
• 선영: 예가 적절하지 않았네 ㅠㅠ 만약 내가 500자리 글자를 암호화 했다고 해봐. 그 때는 나올 수 있는 해석이 정말 많은데, 그걸 언제 다해봐?
• 상근: 얼마나 많은데?
• 선영: 구해보자!

어떤 암호가 주어졌을 때, 그 암호의 해석이 몇 가지가 나올 수 있는지 구하는 프로그램을 작성하시오.

문제 풀이

알고리즘 : 다이나믹 프로그래밍

왜 와이? : 경우의 수를 세고 최적화 위해

설명

1. 입력은 문자열로 받고 for loop 순회를 한다.
2. 현재 인덱스(i) 와 이전 인덱스 (i-1)를 통해 현재 위치에서 26이하인 숫자임을 확인한다.
3. 26이하라면 DP[i] += DP[i-1] + DP[i-2]
   • 두자리 숫자를 쓸 경우와 한자리의 숫자만 쓸경우를 더한다.
4. 26초과라면 DP[i] += DP[i-1]
   • 한자리의 숫자만 사용할 수 있다.

하지만 코드가 옳지 않은 경우 0 을 출력해야한다.

0이 되는 경우

1. 두자리 숫자를 합쳤을 시 26 이상
2. 0이 두번이상 붙어 나올 경우
3. 맨앞에 0 이 나올 경우

또한, 0이 나와도 가능한 경우 0이 아닐 때 사용되는 풀이와 다른 풀이를 적용해야한다.

즉, 한자리 숫자만 쓸 경우는 빼고 생각해야한다.

이렇게 복잡하게 해야하나 싶다. 일단 내 머릿속에 나온거니 정리해본다.

풀이 총정리

1. 문자열로 입력 받아 for loop
2. 현재 인덱스와 이전 인덱스 문자를 조합해 두자리 숫자를 만들어본다.
3. 현재 위치가 0 이거나 이전 위치가 0 이거나 이후 위치가 0 이면 멈출지 말지 본다
4. dp 배열 업데이트

#include <iostream>
#include <string>
using namespace std;

typedef long long ll;

int N;

ll dp[5010];
int main (){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    string str;
    cin >> str;
    dp[0] = 1;
    dp[1] = 1;

    //맨앞자리가 0이면 종료
    if(str[0] == '0'){
        cout << 0;
        return 0;
    }

    for(int i = 1;i<str.size();i++){
            //두자리 숫자 만들어보자
        int one = str[i] - '0';
        int ten = str[i-1] -'0';
        int number = ten * 10 + one;

                //현재 인덱스가 0이라면?
        if(str[i] == '0'){
                //0이어도 26안넘으면 오케이, 하지만 00 이면 탈락
            if(number > 26 || number == 0){
                cout << 0;
                return 0;
            }else{
                    //dp 이월
                dp[i+1] = dp[i];
                continue;
            }
            //이전 인덱스가 0이라면?
        }else if(str[i-1] == '0'){
                //dp 이월
            dp[i+1] = dp[i];
            continue;
            //다음 인덱스가 0이라면?
        }else if(i+1 <= str.size() && str[i+1] == '0'){
            dp[i+1] = dp[i];
            continue;
        }

        if(number > 26){
            dp[i+1] =(dp[i+1] + dp[i] )% rest;
        }else{
            dp[i+1] = (dp[i+1] + dp[i] + dp[i-1]) %rest;
        }
    }
    cout << dp[str.size()];
    return 0;
}

나의 코드가 너무 지저분해서 지피티형에게 수정해달라고 할거다

도와줘요 지피티

#include <iostream>
#include <string>
using namespace std;

typedef long long ll;

const int MOD = 1000000;
ll dp[5001];  // 최대 길이 + 1

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    string s;
    cin >> s;

    if (s.empty() || s[0] == '0') {  // 비어있거나 0으로 시작하면
        cout << 0;
        return 0;
    }

    dp[0] = 1;  // 초기 조건 설정
    dp[1] = 1;

    for (size_t i = 1; i < s.length(); i++) {
        int current = s[i] - '0';  // 현재 문자를 숫자로 변환
        int prev = s[i-1] - '0';  // 이전 문자를 숫자로 변환
        int number = prev * 10 + current;  // 두 자리 수

        if (current == 0) {  // 현재 숫자가 '0'인 경우
            if (number == 0 || number > 26) {  // "00"이거나 "30", "40"...
                cout << 0;
                return 0;
            }
            dp[i+1] = dp[i-1];  // "10"이나 "20"
        } else {  // '0'이 아닌 경우
            dp[i+1] = dp[i];  // 일단 현재 위치에서 이전 위치를 이어 받음
            if (number <= 26 && prev != 0) {  // "10" ~ "26" 사이의 유효한 두 자리 수
                dp[i+1] = (dp[i+1] + dp[i-1]) % MOD;
            }
        }
    }

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

다른점

1. 현재위치에서 0인 경우만 판별
2. 0인경우 dp[i+1] = dp[i-1] 을 통해 두자리 숫자 적용