[JavaScript/DP] 백준 골드 5 : 2011 - 암호 코드

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

2011번: 암호코드

---

📌 작성한 코드 

// 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

 

✅ 성공