https://www.acmicpc.net/problem/2011
2011번: 암호코드
나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다. 암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다.
www.acmicpc.net
📌 작성한 코드
// 2011
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "Beakjoon/Gold/test.txt";
let input = fs.readFileSync(filePath).toString().trim();
const p = input.split("").map(Number);
let flag = false;
const dp = Array(p.length + 1).fill(0);
if (p[0] === 0) flag = true;
dp[0] = 1;
dp[1] = 1;
for (let i = 2; i <= p.length; i++) {
if (p[i - 1] != 0) {
dp[i] += dp[i - 1] % 1000000;
}
let temp = p[i - 2] * 10 + p[i - 1];
if (temp >= 10 && temp <= 26) {
// 두자리 숫자 가능하면
dp[i] += dp[i - 2] % 1000000;
}
}
if (flag) console.log(0);
else console.log(dp[p.length] % 1000000);
📌 설명
삽질, 삽질, 또 삽질하다가 다른 코드 참고해서 푼 풀이.. ㅠㅠ
점화식을 세우는 것까지는 쉬웠으나 0이라는 예외를 처리하는데 너무 복잡한 방법을 사용하여 결국 1시간 내에 푸는 것에 실패하였다. 다른 분들의 코드를 참고하니 너무 간단하고, 정확한 풀이라서 dp는 정말 아이디어 싸움이구나 또 깨달았다.
점화식 세우기
- 암호 코드 중 N번째 문자까지 확인했을 때 가능한 해석 개수를 계산하고자 했을 때 우리는 2가지 경우를 확인해야 한다.
- dp[N]이 N번째 문자까지 확인했을 때 해석의 개수라고 하자.
[1] N-1 암호 코드 개수에 현재 N번째 문자를 덧붙여서 만들기 -> dp[N-1]
[2] N-2 암호 코드 개수에 현재 N문자와 그 앞의 문자(두자리 문자)를 덧붙여서 만들기 -> dp[N-2]

그런데 각 1,2 방법에는 예외가 존재한다. 알파벳은 1부터 시작하기 때문에 0이라는 알파벳이 존재하지 않는다. 그래서 0은 앞의 자리수와 조합한 수에서만 사용할 수 있다(10,20). 그래서 password[n] 숫자를 암호에 덧붙일 때 해당 숫자가 0이라면 dp[N-1]을 더할 수 없다. 또한 앞 글자를 덧붙여서 두 자리수 숫자를 암호에 더하려고 할 때 가능한 알파벳의 범위인 (10 ~26)사이의 숫자가 아니면 dp[N-2]를 더할 수 없다.
dp[0] = 1;
dp[1] = 1;
for (let i = 2; i <= p.length; i++) {
if (p[i - 1] != 0) { // 0이 아닐 때
dp[i] += dp[i - 1] % 1000000;
}
let temp = p[i - 2] * 10 + p[i - 1];
if (temp >= 10 && temp <= 26) { // 조합한 수가 범위 이내일 때
// 두자리 숫자 가능하면
dp[i] += dp[i - 2] % 1000000;
}
}
이렇게 dp에 더하는 방식으로 계산해주면, 올바르지 않은 암호가 나왔을 때 0으로 처리되어서 자연스럽게 예외 처리가 가능하다.
(예를 들어 230과 같은 경우에는 0 -> 한자리수 불가능, 30 -> 두자리수도 불가능 -> dp[3] = 0 => 이렇게 알아서 0으로 예외 처리 된다)
📌 참고
https://g4daclom.tistory.com/161
[알고리즘] 암호코드(백준2011번)_골드5_dp
문제링크 📝 문제 상근이와 선영이가 다른 사람들이 남매간의 대화를 듣는 것을 방지하기 위해서 대화를 서로 암호화 하기로 했다. 그래서 다음과 같은 대화를 했다. 상근: 그냥 간단히 암호화
g4daclom.tistory.com
✅ 성공

'알고리즘 > 백준' 카테고리의 다른 글
| [JavaScript/DP] 백준 골드 5 : 15486 - 퇴사 2 (2) | 2024.02.28 |
|---|---|
| [JavaScript/DP] 백준 골드 5 : 17070 - 파이프 옮기기 1 (1) | 2024.02.27 |
| [JavaScript/DP] 백준 실버 1 : 4883 - 삼각 그래프 (0) | 2024.02.26 |
| [JavaScript/BFS] 백준 골드 2 : 11967 - 불켜기 (1) | 2024.02.26 |
| [JavaScript] 백준 골드 4 : 3190 - 뱀 (0) | 2024.02.24 |