[BOJ 1309] 동물원

문제

동물원

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

 

 

풀이

2 x N 크기의 우리에 사자를 배치하는 경우의 수를 구하는 문제입니다.

 

규칙은 다음과 같습니다.

• 사자들을 우리에 가둘 때, 가로 또는 세로로 붙어있게 배치할 수는 없습니다.
• 한 마리도 배치하지 않는 경우도 하나의 경우의 수로 칩니다.

 

DP를 이용해 해결할 수 있습니다.

 

dp[i]는 i번째 우리에 [사자가 없을 때, 좌측에 있을 때, 우측에 있을 때] 입니다.

dp[1] = [1, 1, 1]로 초기화 해줍니다.

 

점화식은 다음과 같습니다.

 

i번째 우리에 사자가 없을 때, dp[i][0]은 i - 1번째 우리의 모든 경우의 수를 합친 값입니다.

dp[i][0] = dp[i - 1].reduce((acc, cur) => (acc + cur), 0);

 

i번째 우리의 좌측에 사자가 있을 때, dp[i][1]은 i - 1번째 우리에서 사자가 없을 때와 우측에 있을 때의 경우의 수를 합친 값입니다.
dp[i][1] = (dp[i - 1][0] + dp[i - 1][2])

 

i번째 우리의 우측에 사자가 있을 때, dp[i][2]은 i - 1번째 우리에서 사자가 없을 때와 좌측에 있을 때의 경우의 수를 합친 값입니다.
dp[i][2] = (dp[i - 1][0] + dp[i - 1][1])

 

예시 코드

function solution() {
  const n = Number(input());
  const dp = Array.from({ length: n + 1 }, () => Array(3).fill(0));
  // dp[i]는 i번째 우리에 [사자가 없을 때, 좌측에 있을 때, 우측에 있을 때]
  dp[1] = [1, 1, 1];
  const DIVISOR = 9901;

  for (let i = 2; i <= n; i++) {
    dp[i][0] = dp[i - 1].reduce((acc, cur) => (acc + cur) % DIVISOR, 0);
    dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % DIVISOR;
    dp[i][2] = (dp[i - 1][0] + dp[i - 1][1]) % DIVISOR;
  }

  return dp[n].reduce((acc, cur) => (acc + cur) % DIVISOR, 0);
}