[백준] 2011 암호코드 : 자바스크립트(node.js)

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

2011번: 암호코드

 

문제

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

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

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

 

입력

첫째 줄에 5000자리 이하의 암호가 주어진다. 암호는 숫자로 이루어져 있다.

 

출력

나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다.

암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다.

 

풀이 방법

 

암호의 해석이 몇 가지가 나올 수 있는가...

여기서 우선 고려해야 할 조건은 A는 1 Z는 26이기 때문에 26을 벗어나는 숫자는 고려하면 안된다는 거다

즉 382 같은 예시가 들어왔다면 3 8 2 로 끊어서 CHB는 가능하지만 38 2 나 3 82 로는 끊을 수 없다는 거다

이건 다음과 같은 조건 함수로 처리했다

const condition = (idx) => {
  return arr[idx] === "1" || (arr[idx] === "2" && arr[idx + 1] <= "6");
};

 

저기에 들어갈 수 있는 idx 는 주어진 숫자의 길이 - 1 보다 짧아야 한다 (숫자의 길이 - 1 를 인덱스로 갖는애는 제일 마지막 숫자니까 고려할 수 없다)

 

그다음 0에 대한 처리인데 10의 경우 고려가 가능하지만 40의 경우 이 숫자는 해석할 수 없는 숫자에 해당한다

그래서 idx 자체를 + 1 해서 넘기는 대신에 해당 인덱스 자체가 0을 만나면 리턴시켜줬다.

 

를 백트래킹으로 풀어봤다 (dp는 어려워,,)

const input = require("fs")
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./input.txt")
  .toString()
  .trim();

let ans = 0;
let arr = new Array(input.length);
for (let i = 0; i < arr.length; i++) {
  arr[i] = input.charAt(i);
}

const condition = (idx) => {
  return arr[idx] === "1" || (arr[idx] === "2" && arr[idx + 1] <= "6");
};

const recur = (idx) => {
  if (idx > input.length) return;
  if (idx == input.length) {
    ans++;
    return;
  }
  if (arr[idx] === "0") return;

  recur(idx + 1);
  if (idx + 1 < input.length && condition(idx)) {
    recur(idx + 2);
  }
};

const solution = () => {
  recur(0);
  console.log(ans);
};

solution();

 

당연히 시간초과가 날 뿐만 아니라 1000000으로 나눈 나머지를 출력한다. 라는 조건조차 고려하지 않았다

 

ㄷㅏㅇ ㅣ나 ㅁ ㅣ ㅍ ㄹ 그ㄹ ㅐ ㅁ ㅣ

                      ㄱ   ㅡ  ㅗ                ㅇ

ㅠㅠ

사실 풀고나면 간단하긴 한데 백트래킹으로 푼걸 dp로 바꾸는 과정이 조금 생각하기가 어려웠다

여기서 내가 가장 헤맸던 부분은 결국 내가 도출해야 할 값은 dp배열에 들어있는 값이 아니라 만들어질 수 있는 경우의 수를 구하는거였다.

보통 dp문제는 최댓값을 구하는 것일텐데 얘는 모든 경우의수를 구하는 거였다

그래서

if (idx == input.length) {
    return 1;
  }

이부분이 중요했다

모든 조건에 충당하면 1을 리턴시키는 것 => 경우의 수 하나 추가에 해당한다

그리고 이 경우의 수를 dp에 저장하고

if (idx + 1 < input.length && condition(idx)) {
    dp[idx] = recur(idx + 1) + recur(idx + 2);
  } else {
    dp[idx] = recur(idx + 1);
  }

 

저 조건에 해당한다면 두가지 경우의 수 모두를 더해준다

예시로, 2를 만났는데 다음 숫자가 1인 경우 위의 조건절에 해당한다.

그렇기에 2를 선택하고 넘어갔을 경우의 수와 21을 선택하고 넘어갔을 경우의 수를 모두 선택해주는거다

 

만약 조건절에 해당하지 않는 경우는 4 뭐 이런애들을 만났을 때가 되겠다

이런애들은 걍 D 말고는 다른 경우가 없으므로 인덱스만 하나 더해서 저장해주는거다

0을 만나는 경우는 위에서 먼저 리턴시켜줬다

 

최종코드

const input = require("fs")
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./input.txt")
  .toString()
  .trim();

let arr = new Array(input.length);
for (let i = 0; i < arr.length; i++) {
  arr[i] = input.charAt(i);
}

let dp = new Array(input.length).fill(-1);

const condition = (idx) => {
  return arr[idx] === "1" || (arr[idx] === "2" && arr[idx + 1] <= "6");
};

const recur = (idx) => {
  if (idx > input.length) return Number.MIN_SAFE_INTEGER;
  if (idx == input.length) {
    return 1;
  }
  if (arr[idx] === "0") return 0;

  if (dp[idx] !== -1) {
    return dp[idx];
  }

  if (idx + 1 < input.length && condition(idx)) {
    dp[idx] = recur(idx + 1) + recur(idx + 2);
  } else {
    dp[idx] = recur(idx + 1);
  }

  return (dp[idx] %= 1000000);
};

const solution = () => {
  console.log(recur(0));
};

solution();

 

dp는 어려웡