[백준 1073] 도미노 (C#, C++) - soo:bak

문제 링크

1073번 - 도미노

설명

도미노 조각들을 모두 사용하여 사이클 콜렉션을 만들 수 있는 경우의 수를 구하는 문제입니다.

접근법

도미노를 이어 붙여 사이클을 만든다는 것은 같은 숫자끼리 맞닿게 연결해서 처음으로 돌아오는 것입니다. 12, 23, 31 세 조각이 있다면 1-2-3-1로 이어서 사이클 하나를 만들 수 있습니다.

0부터 9까지 숫자를 정점으로, 각 도미노 조각을 양쪽 숫자를 잇는 간선으로 생각하면 그래프 문제가 됩니다. 사이클을 만들려면 각 정점에 연결된 간선이 짝수 개여야 합니다. 들어오는 간선과 나가는 간선이 짝을 이루어야 하기 때문입니다.

0부터 9까지 각 숫자가 도미노에 몇 번 등장하는지 세고, 어떤 숫자라도 홀수 번 등장하면 사이클을 만들 수 없으므로 답은 0입니다.

등장 횟수가 짝수이면, 그 숫자에 연결된 간선들을 짝지어 사이클로 만드는 방법의 수가 정해져 있습니다. 2번이면 1가지, 4번이면 3가지, 6번이면 15가지, 8번이면 105가지입니다. 각 숫자에 대한 경우의 수를 모두 곱하면 답입니다.

---

Code

C#

using System;

class Program {
  static void Main() {
    var cnt = new long[10];
    var table = new long[] {1, 0, 1, 0, 3, 0, 15, 0, 105, 0};

    var n = int.Parse(Console.ReadLine()!);
    for (var i = 0; i < n; i++) {
      var s = Console.ReadLine()!;
      var a = s[0] - '0';
      var b = s[1] - '0';
      cnt[a]++; cnt[b]++;
    }

    var ans = 1L;
    for (var i = 0; i < 10; i++)
      ans *= table[cnt[i]];

    Console.WriteLine(ans);
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

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

  ll cnt[10] = {0, };
  ll table[10] = {1, 0, 1, 0, 3, 0, 15, 0, 105, 0};

  int n; cin >> n;
  for (int i = 0; i < n; i++) {
    string s; cin >> s;
    int a = s[0] - '0';
    int b = s[1] - '0';
    cnt[a]++; cnt[b]++;
  }

  ll ans = 1;
  for (int i = 0; i < 10; i++) ans *= table[cnt[i]];

  cout << ans << "\n";

  return 0;
}