[백준] 9184 신나는 함수 실행 JavaScript

혅·2024년 9월 6일

백준, 프로그래머스 -JavaScript-

목록 보기

135/215

문제

재귀 호출만 생각하면 신이 난다! 아닌가요?

다음과 같은 재귀함수 w(a, b, c)가 있다.

if a <= 0 or b <= 0 or c <= 0, then w(a, b, c) returns:
    1

if a > 20 or b > 20 or c > 20, then w(a, b, c) returns:
    w(20, 20, 20)

if a < b and b < c, then w(a, b, c) returns:
    w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)

otherwise it returns:
    w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)

위의 함수를 구현하는 것은 매우 쉽다. 하지만, 그대로 구현하면 값을 구하는데 매우 오랜 시간이 걸린다. (예를 들면, a=15, b=15, c=15)

a, b, c가 주어졌을 때, w(a, b, c)를 출력하는 프로그램을 작성하시오. 제한 : -50 ≤ a, b, c ≤ 50

입력

입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다.

출력

입력으로 주어진 각각의 a, b, c에 대해서, w(a, b, c)를 출력한다.

예제 입력

1 1 1
2 2 2
10 4 6
50 50 50
-1 7 18
-1 -1 -1

예제 출력

w(1, 1, 1) = 2
w(2, 2, 2) = 4
w(10, 4, 6) = 523
w(50, 50, 50) = 1048576
w(-1, 7, 18) = 1

내가 했던 풀이 방법

a, b, c를 담아둘 배열 abc를 선언하고 input 중에 마지막 줄을 제외하고 a, b, c를 담은 배열을 abc에 추가해준다.
메모제이션을 위해 Map을 초기화한다. (a, b, c를 배열로 저장하게 되면 3차원 배열에 저장해야 하기 때문에 Map으로 "a b c"를 key로 해서 간결하게 해주었다.)
key를 "a b c"로 하고, 만약 Map에 "a b c"가 이미 존재한다면 (이전에 계산된 적이 있다면) 계산 결과를 answer에 더해준다. 만약 존재하지 않는다면 w(a, b, c)를 계산해 더해준다.
w(a, b, c)는 문제 그대로 구현해주면 된다. 다만, 메모제이션을 위해 w(a, b, c)가 이미 Map에 존재한다면 해당 값을 return 해준다. 그 외로는 result에 조건에 맞는 재귀를 선언한 값을 저장한다. result를 해당 key에 value로 Map에 저장해주고, return 해준다.

코드

const fs = require('fs');
let [...input] = fs.readFileSync(0, 'utf-8').toString().trim().split('\n');

let N = input.length - 1;
let abc = [];
for (let i = 0; i < N; i++) {
  let [a, b, c] = input[i].trim().split(' ').map(Number);
  abc.push([a, b, c]);
}

let dp = new Map();

function recursion(a, b, c) {
  let key = `${a} ${b} ${c}`;

  if (dp.has(key)) return dp.get(key);

  let result;

  if (a <= 0 || b <= 0 || c <= 0) {
    result = 1;
  } else if (a > 20 || b > 20 || c > 20) {
    result = recursion(20, 20, 20);
  } else if (a < b && b < c) {
    result = recursion(a, b, c - 1) + recursion(a, b - 1, c - 1) - recursion(a, b - 1, c);
  } else {
    result =
      recursion(a - 1, b, c) + recursion(a - 1, b - 1, c) + recursion(a - 1, b, c - 1) - recursion(a - 1, b - 1, c - 1);
  }

  dp.set(key, result);
  return result;
}

let answer = '';
for (let i = 0; i < N; i++) {
  let key = `${abc[i][0]} ${abc[i][1]} ${abc[i][2]}`;
  answer += `w(${abc[i][0]}, ${abc[i][1]}, ${abc[i][2]}) = `;
  if (dp.has(key)) answer += dp.get(key) + '\n';
  else answer += recursion(abc[i][0], abc[i][1], abc[i][2]) + '\n';
}

console.log(answer.trim());