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

🧮 문제

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

9184번: 신나는 함수 실행

 

지 혼자만 냅다 신나버린 9184번 문제..🙂🔥

 

9184번은 *메모이제이션(Memoization)을 이용해 푸는 전형적인 동적계획법(DP, Dynamic Programing) 문제라고 한다.

* 동일한 문제를 반복해야 할 경우, 한 번 계산된 결과를 저장해 두었다가 활용하는 방식으로 중복 계산을 줄이는 것

 

 

 

✍🏻 풀이

입력값

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

 

 

두 번째 예제 입력값을 통해 예제를 먼저 이해해보기로 했다.

 

2 2 2 는 문제의 네 조건 중 마지막에 해당되므로 일단 함수에 맞게 값을 넣는다.

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)

 

 

그럼 아래와 같이 식이 나온다.

w(1, 2, 2) + w(1, 1, 2) + w(1, 2, 1) - w(1, 1, 1)

 

 

여기서 또 각 재귀함수의 a, b, c값을 문제의 조건에 해당되는 것이 있는지 맞춰보는 것이다.

w(1, 2, 2) = w(0, 2, 2) + w(0, 1, 2) + w(0, 2, 1) - w(0, 1, 1) //2
w(1, 1, 2) = w(0, 1, 2) + w(0, 0, 2) + w(0, 1, 1) - w(0, 0, 1) //2
w(1, 2, 1) = w(0, 2, 1) + w(0, 1, 1) + w(0, 2, 0) - w(0, 1, 0) //2
w(1, 1, 1) = w(0, 1, 1) + w(0, 0, 1) + w(0, 1, 0) - w(0, 0, 0) //2

문제의 조건에서 a, b, c중 하나라도 0 이하이면 1을 출력한다고 하였으므로 각 재귀함수는 2라는 결과값을 가진다.

그럼 2 + 2 + 2 - 2가 되어서 출력값인 4가 나오게 되는 것이다.

 

이렇게 예제를 이해하고나니까, 어떻게 동적계획법이 사용되는지 알 것 같았다 !

 

 

 

 

💡 코드

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().split('\n');

let readlineIdx = 0;
const readInput = () => input[readlineIdx++];

// 함수 w에서 a, b, c 중 20이 넘어가게 되면 w(20, 20, 20)을 호출하고, 0 이하일 경우는 1을 반환하기 때문에
// 각 배열의 크기가 21 (0~20)을 넘기지 않는다.
let arr = new Array(21);  // 21개의 요소를 갖는 배열을 생성함

// 문제 내 재귀함수들 나열
function w(a, b, c) {
  if (a <= 0 || b <= 0 || c <= 0) {
    return 1;
  }
  
  if (a > 20 || b > 20 || c > 20) {
    return w(20, 20, 20);
  }

  // 이미 계산되어 저장되어있는 경우 해당 값을 바로 반환(메모이제이션)
  if (arr[a][b][c] !== 0) {
    return arr[a][b][c];
  }

  if (a < b && b < c) {
    let t1 = arr[a][b][c - 1] = w(a, b, c - 1);
    let t2 = arr[a][b - 1][c - 1] = w(a, b - 1, c - 1);
    let t3 = arr[a][b - 1][c] = w(a, b - 1, c);
    return arr[a][b][c] = t1 + t2 - t3;
  }

  let t1 = arr[a - 1][b][c] = w(a - 1, b, c);
  let t2 = arr[a - 1][b - 1][c] = w(a - 1, b - 1, c);
  let t3 = arr[a - 1][b][c - 1] = w(a - 1, b, c - 1);
  let t4 = arr[a - 1][b - 1][c - 1] = w(a - 1, b - 1, c - 1);
  
  return arr[a][b][c] = t1 + t2 + t3 - t4;
}

function main() {
  for (let i = 0; i < 21; ++i) {
    arr[i] = new Array(21); // 각각의 요소마다 21개의 요소를 가지는 배열을 생성함
    for (let j = 0; j < 21; ++j) {
      arr[i][j] = new Array(21).fill(0); // 21개의 요소를 0으로 채움
    }
  }
  while (true) {
    let [a, b, c] = readInput().split(' ');
    a = Number(a);
    b = Number(b);
    c = Number(c);
    if (a === -1 && b === -1 && c === -1) break;
    
    console.log(`w(${a}, ${b}, ${c}) = ${w(a, b, c)}`);
  }
}

main();

 

 

 

📍 참고

https://velog.io/@chelsea/1-동적-계획법Dynamic-Programming-DP

[자료구조와 알고리즘] 동적 계획법(Dynamic Programming, DP)

 

https://st-lab.tistory.com/190

[백준] 9184번 : 신나는 함수 실행 - JAVA [자바]

 

https://pkiop.tistory.com/217

백준 9184 신나는 함수실행 javascript

 

http://www.tcpschool.com/javascript/js_array_application

코딩교육 티씨피스쿨