[백준][DP] 2011 암호코드 NodeJs 구현

목차

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

문제

 

풀이 할 때 도움이 되는 조건

//내가 생각해야 할것은 현재와 이전의 것들
//1203
// 0앞에 아무것도 안오는 경우 (즉, 맨앞자리가 0인 경우):
// 05, 035, 017 이런건 0을 어떻게 분할 해도 0이 알파벳으로 변환이 안 되니깐 0이 출력 돼야 합니다

// 0 앞에 0이 오는 경우:
// 0024, 10025, 17200312 같은 경우 00을 어떻게 분할 해도 (예: 10025 --> 10 0, 1 00, 1 00) 0이 남아서 오류가 납니다. 고로 0이 출력돼야 합니다.

// 0앞에 1이나 2가 오는 경우:
// 10, 20 은 알파벳으로 변환이 돼서 경우의 수가 만들어 질 수 있습니다.

// 예시: 20114 --> 정답: 3   /   1010 --> 정답: 1   /   111012 --> 정답: 4

// 0앞에 3이나 더 큰 숫자가 오는 경우:
// 302는 어떻게 분할 해도 30 2, 3 02, 3 0 2 알파벳으로 변환이 안됩니다. 고로 0이 출력.

// 다른 예시: 1131212501112122 --> 정답: 0

 

문제 구현 방향

문제 포인트는 dp를 통해 해당의 인덱스가 아닌 다음 인덱스에 누적하는 것이다.

 

일단 처음에 0이 오면 0을 반환한다. 

if (arr[0] === 0) {
  console.log(0);
  return;
}

 

그 이후부터 생각해보자 

1 2 0 3 7이 있다고 하면 문자열 예외는 다음만 고려하면 된다.

12 20 03 37

10이상 26이하가 되면 누적해야 한다는 것을 도출할 수 있다.

 

dp[0] = dp[1] = 1;

 

그 이후 1, 3에 대해 생각 해보자

d[2] = dp[1]+dp[0]

 

이번에는 3, 1에 대해 생각 해보자

dp[2] = dp[1]

 

그러면 dp[i-1]을 먼저 받고

예외 조건을 확인한 후 dp[i-2]를 더해주면 될 것 같다.

 

이번에는 1, 3, 0 에 대해 생각 해보자 0보다 큰게 앞에 있으면 무조건 0이다.

dp[3] = 0

 

그후 1, 3, 0, 2에 대해 생각 해보자

dp[4] = dp[3] 그렇다 이후 계속 0이 나온다.

 

이번에는 3, 1, 0에 대해 생각 해보자 

dp[3] = 0 (arr[i-1] => 0)

dp[3] = dp[3] + dp[1] (10)

 

그 후 3, 1, 0, 2 에 대해 생각 해보자

dp[4] = dp[3] =1 (arr[i-1] !=0)

dp[4] = dp[4] + dp[2]  (02)

 

 

코드 구현

const input = require("fs")
  .readFileSync("./dev/stdin", "utf-8")
  .trim()
  .split("\n");
let arr = input[0].trim().split("").map(Number);
let dp = new Array(5003).fill(0);
let MOD = 1000000;
if (arr[0] === 0) {
  console.log(0);
  return;
}
dp[0] = dp[1] = 1;

for (let i = 2; i <= arr.length; i++) {
  if (arr[i - 1] != 0) {
    dp[i] = dp[i - 1] % MOD;
  }
  let tmp = arr[i - 2] * 10 + arr[i - 1];
  if (tmp >= 10 && tmp <= 26) {
    dp[i] = (dp[i] + dp[i - 2]) % MOD;
  }
}
console.log(dp[arr.length]);