백준 1309 < 동물원 > JavaScript

📍문제 링크

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

1309번: 동물원

 

📍알고리즘 분류

- 다이나믹 프로그래밍

 

📍문제 풀이

- 자연수 N이 주어질 때,  2 * N 배열에 원소를 채우는 경우의 수를 9901로 나눈 나머지를 구하라

- 원소는 가로나 세로로 붙을 수 없다

- 원소를 하나도 배치하지 않은 경우도 한 가지의 경우의 수로 친다

 

N =1 일 때의 결과를 N = 2 일 때 이용할 수 있다면, DP로 해결할 수 있다

 

"""
N = 1

1. 0,0 좌표에 사자 배치
OX

2. 0,0 좌표에 사자 no배치
XO

3. no배치
XX
------------
N = 2

N = 1의 경우에다 밑에 블록을 붙일건데
all XX 가능한 경우의 수는 => 모두 가능
+dp(1) = + 3

OX 가능한 경우의 수는 => XO, XX (N1.2 + N1.3)
+2 (1 + 1)

XO 가능한 경우의 수는 => OX, XX (N1.1 + N1.3)
+2 (1 + 1)

즉, dp(2) = dp(1) + 2 + 2 = 7
-----------------
N = 3

N = 2의 경우에다 밑에 블록을 붙일건데
all XX 가능한 경우의 수는 => 모두 가능
+dp(2) = + 7

OX 가능한 경우의 수는 => XO, XX (N2.2 + N2.3)
+5 (2 + 3)

XO 가능한 경우의 수는 => OX, XX (N2.1 + N2.3)
+5 (2 + 3)

즉, dp(3) = dp(2) + 5 + 5 = 17

이차원 배열을 만들면,
dp = [
    [0, 0, 0],
    [1, 1, 1],
    [dp[1]의 총합, dp[1][0] + dp[1][1], dp[1][0] + dp[1][2],
    [dp[2]의 총합, dp[2][0] + dp[2][1], dp[2][0] + dp[2][2].
    ...
]
"""

 

📍1트 -> 메모리 초과

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let input = 0;

rl.on("line", (line) => {
  input = line;
}).on("close", () => {
  const N = +input;
  const memo = Array.from({ length: N + 1 }, (_) => [0n, 0n, 0n]);
  memo[1] = [1n, 1n, 1n];
  for (let i = 2; i <= N; i++) {
    memo[i][0] += BigInt(memo[i - 1][0] + memo[i - 1][1] + memo[i - 1][2]);
    memo[i][1] += BigInt(memo[i - 1][0] + memo[i - 1][1]);
    memo[i][2] += BigInt(memo[i - 1][0] + memo[i - 1][2]);
  }
  console.log(((memo[N][0] + memo[N][1] + memo[N][2]) % 9901n).toString());
});

 

배열을 너무 많이 늘려서 사용한 탓인지 메모리 초과 발생...

memo[i][1] 과 memo[i][2]는 어찌 보면 같은 값이기 때문에 하나로 퉁치고, *2를 활용해서 대체할 수 있다

또한 배열을 굳이 쭉 늘여 사용할 필요 없이 변수를 활용해도 된다

 

또한 수가 커지기 때문에 BigInt를 사용해야 한다!

 

📍2트 -> 성공

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let input = 0;

rl.on("line", (line) => {
  input = line;
}).on("close", () => {
  const N = +input;
  let memoA = 1n;
  let memoB = 1n;
  for (let i = 2; i <= N; i++) {
    const prevA = memoA;
    const prevB = memoB;
    memoA = BigInt(prevA + prevB * 2n);
    memoB = BigInt(prevA + prevB);
  }
  console.log(((memoA + memoB * 2n) % 9901n).toString());
});

 

📍리뷰

- 메모리 제한이 빡빡할 때는 배열 대신 변수를 사용해서 메모리를 줄일 수 있다!