[알고리즘] 백준 14651 걷다보니 신천역 삼 (Large)

📖문제

걷다보니 신천역 삼

❓구상

N자리수의 숫자에서 0, 1, 2 만 가지고 만들 수 있는 3의 배수의 갯수를 출력해야 하는데 일정 패턴이 있는지 파악을 하면 동적 프로그래밍을 활용하면 문제를 풀 수 있을 것으로 생각된다. 우선, 입력값 N 에 따른 출력 갯수를 파악하기 위해 백트래킹으로 출력값을 파악해보기로 했다.

 

패턴파악을 위한 백트래킹을 사용한 코드.

const result = [];
const N = 10;
const backTracking = (arr, line) => {
  if (line.length !== N) {
    const len = arr.length;
    for (let i = 0; i < len; i++) {
      const copyArr = [...arr];
      const copyLine = [...line];
      const num = copyArr[i];
      copyLine.push(num);
      backTracking(copyArr, copyLine);
    }
  } else {
    if (line[0] !== 0) {
      const num = +line.join("");
      !(num % 3) && result.push(num);
    }
    line = [];
  }
};
backTracking([0, 1, 2], []);
console.log(result.filter((e) => !(e % 3)).length % 1000000009);

 

 

출력

위의 코드로 N이 2, 4, 5, 6, 7, 8, 9 일때의 결과를 확인함으로 1에서 10 까지 N에 따른 출력값을 파악할 수 있었다.

1 -> 0
2 -> 2
3 -> 6
4 -> 18
5 -> 54
6 -> 162
7 -> 486
8 -> 1458
9 -> 4374
10 -> 13122

 

+ ) 백트래킹으로도 이 문제가 요구하는 출력값을 충족시킬 수 있어 추가로 제출해 보았다.

결과는 메모리 초과 

이유는 동적 계획법은 공간복잡도가 저장해야할 메모리 크기에 의해 결정되는데 백트래킹은 재귀 호출에 사용되는 호출 스택 크기와 선택지를 저장하는 데 필요한 공간에 따라 결정되기 때문이다.

즉, 동적 계획법은 공간복잡도가 O(n) 이지만 백트래킹은 O(d) (d : 탐색의 최대 깊이) 이다.

백트래킹으로 시도한 코드를 보면 

if (line.length !== N)

line 배열의 길이가 N 을 만족할 때 까지 재귀 호출을 반복 한다.

특히나 이 문제는 N 의 범위가 1 이상 33,333 이하의 조건이 있기 때문에 적당한 수준의 N 이 입력된다면 백트래킹으로도 충분히 커버가 가능하겠으나, N 의 값이 커지는 경우 중복계산이 많아지게되고 성능 저하 및 스택 오버플로우가 발생 할 수 있다.

 

그렇기 때문에 백트래킹으로 알아낸 출력값으로 동적계획법을 사용하여 문제를 해결하는 것이 옳바를 것이다.

코드.

const N = +require("fs").readFileSync("./input.txt", "utf-8").trim();
const dp = [0, 2];
const solution = (n) => {
  for (let i = 2; i < n; i++) {
    if (dp[i]) dp[i];
    else dp[i] = (dp[i - 1] * 3) % 1000000009;
  }
};
solution(N);
console.log(dp[N - 1]);

 

패턴을 파악해보니 f(i) 의 값은 f(i - 1) 의 값에 3 을 곱한 값과 같은 것을 알 수 있었다.

dp 배열의 초깃값을 [0, 2] 로 설정해주었고, 인덱스는 항상 0부터 시작하기 때문에 dp 배열의 N - 1 번째 값을 출력해 문제를 해결했다.

 

개선코드.

작성했던 코드를 살펴보던 중 문제에서는 

숫자가 너무 커질 수 있기에 dp[N-1] 의 값을 10^8 + 9(1,000,000,009) 로 나눈 값의 나머지를 출력하라고 한다.

다행이 위의 코드로도 문제는 없이 출력되었고 재확인 해본 결과 N이 33,333인 경우에도 출력값은 동일했지만 문제의 조건에 좀더 적절하게 코드를 아래와 같이 수정했다.

const N = +require("fs").readFileSync("./input.txt", "utf-8").trim();
const dp = [0n, 2n];
const solution = (n) => {
  for (let i = 2; i < n; i++) {
    if (dp[i]) dp[i];
    else dp[i] = dp[i - 1] * 3n;
    // 기존 코드 : else dp[i] = (dp[i - 1] * 3) % 1000000009;
  }
};
solution(N);
console.log(`${dp[N - 1] % 1000000009n}`);
// 기존 코드 : console.log(`${dp[N - 1]}`);

 

🔥배운 점

연달아 동적계획법 관련 알고리즘을 풀고 있는데, 이번 문제는 동적계획법을 사용하는 것이 옳은 방식이였지만 백트래킹을 사용해서 성능은 떨어지지만 다양한 접근법으로 문제를 바라볼 수 있었던것 같다. 특히, 평소에 백트래킹을 이용해서 문제를 해결할때 DP를 사용해서도 풀 수 있는 문제를 가끔 본적 있는데 백트래킹을 사용하는 이유에 대해 궁금은 했지만, 크게 파고들지 않았는데

백트래킹은 검색 범위가 크지 않거나 조건에 따라 탐색을 빠르게 줄일 수 있거나, 문제를 탐색하며 풀어가는 것이 자연스러운 경우 적합하고,

동적계획법은 하위 문제의 결과를 재활용해야 하는 경우나 문제 크기가 크더라도 메모리를 더 신중하게 관리할 수 있는 구조가 있는 경우 적합하다. 이 점을 잊지말고 각각의 케이스에 맞게 효율적인 해결법을 적용하는 연습을 해야겠다.