시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB72574994.231%

문제

마작은 $14$장의 패를 모아 용을 만드는 게임입니다. 용을 만들기 위해서는 패, 머리, 몸통에 대해 알아야 합니다.

  • 패牌: 마작에는 $1$ 이상 $9$ 이하의 수가 적힌 패가 각각 $4$장씩 있습니다.
  • 머리: 같은 수가 적힌 패 $2$장의 조합을 말합니다(예: 44).
  • 몸통: $1$씩 차이가 나는 연속된 수가 적힌 패 $3$장(예: 678) 혹은 같은 수가 적힌 패 $3$장(예: 222)의 조합을 말합니다. 패의 순서는 중요하지 않습니다.

다음은 머리 혹은 몸통인 것과 그렇지 않은 것의 예를 나타냅니다.

예시 구분 설명
2 - 패가 $1$장이므로 머리도 몸통도 될 수 없습니다.
22 머리 같은 패 $2$장이 있으므로 이 두 패의 조합은 머리입니다.
789 몸통 $7,8,9$는 $1$씩 차이가 나는 연속된 수이므로 이 세 패의 조합은 몸통입니다.
135 - $1,3,5$는 $1$씩 차이가 나는 연속된 수가 아니므로 이 세 패의 조합은 몸통이 아닙니다.
891 - $9$와 $1$은 서로 연속된 수가 아닙니다.
999 몸통 같은 패 $3$장이 있으므로 이 세 패의 조합은 몸통입니다.
454 - $4,4,5$는 $1$씩 차이가 나는 연속된 수가 아니므로 이 세 패의 조합은 몸통이 아닙니다.
8888 - 패가 $4$장이므로 머리도 몸통도 될 수 없습니다.

이제 용을 만들기 위해서는 패 $14$장을 머리 $1$개와 몸통 $4$개 혹은 서로 다른 머리 $7$개의 조합으로 만들어야 합니다.

다음은 용과 용이 아닌 예를 나타냅니다.

33444566777889: 용
  • 머리 $(3,3)$과 몸통 $(4,4,4) ;(5,6,7) ;(6,7,8) ;(7,8,9)$로 이루어진 용입니다.
11123455577778: 용이 아님
  • 어떻게 분할을 해도 머리 $1$개와 몸통 $4$개 혹은 머리 $7$개를 만들 수 없기 때문에 용이 아닙니다.
  • 같은 패가 $2$개 이상의 머리 혹은 몸통에 동시에 속해서는 안 됩니다.
11223355778899: 용
  • 머리 $(5,5)$와 몸통 $(1,2,3) ;(1,2,3) ;(7,8,9) ;(7,8,9)$으로 이루어진 용입니다.
  • 서로 다른 머리 $7$개인 $(1,1) ;(2,2) ;(3,3) ;(5,5) ;(7,7) ;(8,8) ;(9,9)$로 이루어진 용으로 볼 수도 있습니다.
11112255668899: 용이 아님
  • 머리 $7$개를 만들기 위해서는 중복된 두 개의 머리 $(1,1)$을 만들어야 하기 때문에 머리가 $7$개인 용이 될 수 없습니다.
  • 어떻게 분할을 해도 머리 $1$개와 몸통 $4$개를 만들 수 없기 때문에 용이 아닙니다.

현재 패산에는 패가 $N$장 쌓여 있고, $i$번째 패에는 $A_i$가 적혀 있습니다. 여러분은 여기서 $14$장의 패를 뽑아 용을 만들 수 있는 경우의 수가 몇 가지인지 알고 싶어졌습니다.

입력

첫 번째 줄에 패산에 있는 패의 개수 $N$이 주어집니다. $(14\le N\le 36)$

두 번째 줄에 $A_1,A_2,\cdots ,A_N$이 공백으로 구분되어 주어집니다. $(1\le A_i\le 9)$ 한 종류의 패가 $4$장 초과로 주어지지 않습니다.

출력

패산에서 $14$장의 패를 뽑아 용을 만들 수 있는 경우의 수를 출력합니다.

예제 입력 1

14
1 1 2 2 3 3 5 5 7 7 8 8 9 9

예제 출력 1

1

예제 입력 2

36
4 1 6 1 5 3 9 5 9 2 9 9 7 4 5 3 3 2 1 7 8 4 5 7 8 6 3 1 2 8 6 7 2 4 8 6

예제 출력 2

445632532

노트

  • 패에 적힌 수의 조합이 같아도 다른 위치의 패를 뽑은 경우에는 서로 다른 경우로 셉니다.
  • 패 $14$장을 뽑았을 때 용을 여러 종류의 조합으로 만들 수 있어도 하나의 경우로 셉니다.

출처

Contest > BOJ User Contest > 마작컵 > 마작컵 2024 - 우인전 3/4 님만 오면 ㄱ 1s번