[BOJ] 10220번: Self Representing Seq

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

이 문제는 정말 수학문제입니다. 수열의 갯수를 계산해야 하는데, $A[0]$의 값으로 경우의 수를 나눠야합니다.

$A[0]$이 $0$인 경우는 자명하게 불가능합니다.($A[0]$이 0이라는 것은 $A[0]$~$A[N-1]$중에 0이 없다는 소리인데 당장 $A[0]$이 0이므로 모순)

i) $A[0] = 1$일 때 

0은 딱 1번 나오므로 $A[1],A[2], ... , A[N-1]$ 중에서 1개는 0, 1개는 2, $N-3$개는 1임을 알 수 있습니다. 그렇게 되면 $A[1] = N-2$ 인데, $A[1]$은 1 혹은 2이므로 $N-2$는 1 혹은 2이므로 $N = 3, 4$일 때 실제로 확인해보면 $N = 3$일땐 불가능하고 $N = 4$일 땐 (1,2,1,0)이 가능함을 확인할 수 있습니다. 

ii) $A[0] = 2$일 때 

0은 2번 나오므로 $A[1],A[2], ... , A[N-1]$ 중에서 2개는 0, 1개는 2, $N-4$개는 1임을 알 수 있습니다. 그렇게 되면 $A[1] = N-4$, $A[2] = 2$가 됩니다. $A[1]$은 0 혹은 1혹은 2이므로 $N = 4,5,6$에 대해서 실제로 확인해보면 $N=4$일땐 (2,0,2,0), $N=5$일땐 (2,1,2,0,0), $N=6$일땐 불가능합니다. 

iii) A0 > 2일 때 

 $A[1],A[2], ... , A[N-1]$ 중에서 정확히 $A[0]$개가 0. 나머지 $N-1-A[0]$개의 원소의 합은 $N-A[0]$이므로 딱 하나만 2이고 나머지는 전부 1이어야 합니다. 

그러면 0는 $A[0]$번, 1은 $N-2-A[0]$번, 2는 1번, $A[0]$는 1번, 나머지 수는 0번 등장합니다. 

그런데 딱 하나만 2이고 나머지는 전부 1이어야 하므로 $N-2-A[0]$ = 2가 되고 계산하면 $A[0] = N-4$가 되어서 최종적으로 

$A[0] = N-4, A[1] = 2, A[2] = 1, A[N-4] = 1$이면 됩니다. 단 $N > 6$이어야겠네요. 

최종적으로 $N$이 1,2,3,6일땐 0이고, $N$이 4일땐 2이고, 나머지 $N$에 대해서는 1이네요.

https://github.com/encrypted-def/BOJ/blob/master/10220.cpp