백준 10220 Self Representing Seq python3

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

10220번: Self Representing Seq

처음에 문제가 무슨 말인가 싶었던 문제였습니다. 

아무래도 플레 문제이다 보니 좀 어려운가 싶었는데 채점현황을 보니 다들 코드가 짧았습니다.

그 말은 뭔가 숨은 규칙이 있다는 뜻인거 같습니다.

 

1개씩 해보면,

n=1 => 0

n=2 => 0

n=3 => 0

n=4 => 2

n=5 => 1

n=6 => 0 인 것은 쉽게 찾을 수 있고,

n=7 => (3,2,1,1,0,0,0) 케이스 밖에 없고

n=8 => (4,2,1,0,1,0,0,0) 케이스 밖에 없습니다.

 

일단 규칙 상 0,1,2 등 작은 수를 최대한 많이 가져가는 게 좋아보입니다.

규칙 상으로는 A0 = n-4 인데, 이외의 경우가 있나 계산해보면, 

A0 = n-k (k != 4) 라고 잡으면, 나머지 n-1 개 숫자 중 0인 값이 총 n-k 개 존재해야 합니다. 

그리고 A(n-k) = 1 입니다.

그러므로 n-2 - (n-k) = k - 2 개는 0이 아닌 숫자입니다.

 

1) k-2 개 숫자 중 1이 0개인 경우이면, A1 = 0 이고, 이는 모순입니다.

2) k-2 개 숫자 중 1이 1개인 경우이면, A1 = 1입니다.

---- 나머지 k-3 개 숫자 중 2가 0개인 경우이면, A2 = 0 이고, 모순입니다.

---- 나머지 k-3 개 숫자 중 2가 1개인 경우이면, A2 = 1 이고, 모순입니다.

---- 나머지 k-3 개 숫자 중 2가 2개인 경우이면, A2 = 2 이고, 나머지 k-4 개 숫자 중 2가 1개 더 나와야 합니다.

---- 하지만 나머지 수 중 2가 1번 더 나오면, 그 수만큼 또 수가 나와야 함이 반복되므로, 결국 k-3 개 내에서 나올 수 있는 경우의 수는 0입니다.

 

3) k-2 개 숫자 중 1이 2개인 경우이면, A1 = 2, A2 = 1 입니다.

나머지 k-4 개 숫자 중 0이 아닌 수가 나오면, 그 수만큼 또 카운트가 되어야 하므로 k-4=0 이 되어야 합니다.

 

따라서, A0=n-4, A1=2, A2=1, A(n-4)=1, 나머지 0 인 경우만 존재합니다.

 

위 내용이 증명이라기에는 좀 빈약하지만, 작은 수를 최대한 많이 가져가야 한다는 가정은 맞는 추론이라 생각됩니다.

(큰 수를 Ai 가 갖는다면, 그만큼 i를 갖는 Aj 가 존재해야 하고, j 값을 갖는 Ak 가 존재해야 하고, ...., 이것이 계속 반복되면 조건 만족 못 함.)

 

코드는 아래와 같습니다.

T = int(input())
for _ in range(T) :
  n = int(input())
  if n == 1 or n == 2 or n == 3 or n == 6:
    print(0)
  elif n == 4:
    print(2)
  else:
    print(1)