[백준 1309] 동물원 (C#, C++) - soo:bak

문제 링크

1309번 - 동물원

설명

2행 N열의 우리가 있을 때, 사자들을 가로세로로 붙지 않게 배치하는 경우의 수를 구하는 문제입니다.

각 칸에는 사자를 배치할 수도 있고 비워둘 수도 있지만,

같은 줄(가로)이나 같은 열(세로)에 바로 인접한 칸에는 사자를 둘 수 없습니다.

사자를 한 마리도 배치하지 않는 경우도 유효한 하나의 배치로 간주됩니다.

접근법

동적 계획법(DP)을 활용해 풀이할 수 있는 문제입니다.

n열까지 사자를 배치하는 경우의 수를 상태로 정의하고,

이전에 어떻게 배치했는지를 바탕으로 다음 배치 가능성을 구성합니다.

각 열(세로줄)을 기준으로 3가지 상태를 생각할 수 있습니다:

• 해당 열에 왼쪽 칸에만 사자를 둔 경우
• 해당 열에 오른쪽 칸에만 사자를 둔 경우
• 해당 열에 사자를 두지 않은 경우

이전 열의 상태에 따라 현재 열의 가능한 상태를 계산하면서 한 열씩 오른쪽으로 확장해갑니다.

마지막 열에서 가능한 모든 상태의 경우의 수를 더하면 전체 경우의 수가 됩니다.

결과는 9901로 나눈 나머지를 출력해야 하므로, 모든 연산 과정에서도 동일하게 나머지를 적용합니다.

---

Code

C#

using System;

class Program {
  static void Main() {
    int n = int.Parse(Console.ReadLine());
    int[,] dp = new int[n, 3];
    for (int i = 0; i < 3; i++) dp[0, i] = 1;

    for (int i = 1; i < n; i++) {
      dp[i, 0] = (dp[i - 1, 1] + dp[i - 1, 2]) % 9901;
      dp[i, 1] = (dp[i - 1, 0] + dp[i - 1, 2]) % 9901;
      dp[i, 2] = (dp[i - 1, 0] + dp[i - 1, 1] + dp[i - 1, 2]) % 9901;
    }

    int res = (dp[n - 1, 0] + dp[n - 1, 1] + dp[n - 1, 2]) % 9901;
    Console.WriteLine(res);
  }
}

C++

#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n; cin >> n;

  vvi dp(n, vi(3, 1));
  for (int i = 1; i < n; ++i) {
    dp[i][0] = (dp[i-1][1] + dp[i-1][2]) % 9901;
    dp[i][1] = (dp[i-1][0] + dp[i-1][2]) % 9901;
    dp[i][2] = (dp[i-1][0] + dp[i-1][1] + dp[i-1][2]) % 9901;
  }

  cout << (dp[n-1][0] + dp[n-1][1] + dp[n-1][2]) % 9901 << "\n";

  return 0;
}