반응형
2011번: 암호코드
나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다. 암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다.
www.acmicpc.net
문제
상근이와 선영이가 다른 사람들이 남매간의 대화를 듣는 것을 방지하기 위해서 대화를 서로 암호화 하기로 했다. 그래서 다음과 같은 대화를 했다.
- 상근: 그냥 간단히 암호화 하자. A를 1이라고 하고, B는 2로, 그리고 Z는 26으로 하는거야.
- 선영: 그럼 안돼. 만약, "BEAN"을 암호화하면 25114가 나오는데, 이걸 다시 글자로 바꾸는 방법은 여러 가지가 있어.
- 상근: 그렇네. 25114를 다시 영어로 바꾸면, "BEAAD", "YAAD", "YAN", "YKD", "BEKD", "BEAN" 총 6가지가 나오는데, BEAN이 맞는 단어라는건 쉽게 알수 있잖아?
- 선영: 예가 적절하지 않았네 ㅠㅠ 만약 내가 500자리 글자를 암호화 했다고 해봐. 그 때는 나올 수 있는 해석이 정말 많은데, 그걸 언제 다해봐?
- 상근: 얼마나 많은데?
- 선영: 구해보자!
어떤 암호가 주어졌을 때, 그 암호의 해석이 몇 가지가 나올 수 있는지 구하는 프로그램을 작성하시오.
문제 풀이
알고리즘 : 다이나믹 프로그래밍
왜 와이? : 경우의 수를 세고 최적화 위해
설명
- 입력은 문자열로 받고 for loop 순회를 한다.
- 현재 인덱스(i) 와 이전 인덱스 (i-1)를 통해 현재 위치에서 26이하인 숫자임을 확인한다.
- 26이하라면 DP[i] += DP[i-1] + DP[i-2]
- 두자리 숫자를 쓸 경우와 한자리의 숫자만 쓸경우를 더한다.
- 26초과라면 DP[i] += DP[i-1]
- 한자리의 숫자만 사용할 수 있다.
하지만 코드가 옳지 않은 경우 0 을 출력해야한다.
0이 되는 경우
- 두자리 숫자를 합쳤을 시 26 이상
- 0이 두번이상 붙어 나올 경우
- 맨앞에 0 이 나올 경우
또한, 0이 나와도 가능한 경우 0이 아닐 때 사용되는 풀이와 다른 풀이를 적용해야한다.
즉, 한자리 숫자만 쓸 경우는 빼고 생각해야한다.
이렇게 복잡하게 해야하나 싶다. 일단 내 머릿속에 나온거니 정리해본다.
풀이 총정리
- 문자열로 입력 받아 for loop
- 현재 인덱스와 이전 인덱스 문자를 조합해 두자리 숫자를 만들어본다.
- 현재 위치가 0 이거나 이전 위치가 0 이거나 이후 위치가 0 이면 멈출지 말지 본다
- 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;
}
다른점
- 현재위치에서 0인 경우만 판별
- 0인경우 dp[i+1] = dp[i-1] 을 통해 두자리 숫자 적용
반응형
'BOJ' 카테고리의 다른 글
| [코드트리] 마법의 숲 탐색 (3) | 2024.09.15 |
|---|---|
| [BOJ 1011] Fly me to the Alpha Centauri (0) | 2024.08.11 |
| [BOJ 2531] 회전 초밥 (0) | 2024.03.08 |
| [BOJ 2146] 다리 만들기 (0) | 2024.01.26 |
| [백준 1018번] 체스판 다시 칠하기 (0) | 2021.05.03 |
