[백준 10220번] Self Representing Seq (Python3)

import sys
input = sys.stdin.readline

def DFS(now,SUM):
  global result
  for i in range(N):
    if cnt[i]==seq[i]:
      continue
    if cnt[i]>seq[i] and i<now or SUM+i>N or now==N:
      return
    cnt[i] += 1
    seq[now] = i
    DFS(now+1,SUM+i)
    cnt[i] -= 1
    seq[now] = -1
  if now==N:
    result += 1
    
for _ in range(int(input())):
  N = int(input())
  if N<10:
    seq = [-1]*N; cnt = [0]*N; result = 0
    DFS(0,0)
    print(result)
  else:
    print(1)

재미있는 문제였다.

브루트 포스? 로 해결하였다.

 

mod는 페이크일 것이라고 생각하였다. 왜냐하면 딱봐도 10**9+7이라는 값에 근접하지 조차 못할 것으로 보였기 때문이다. 따라서 브루트 포스로 해결할 수 있을 것이라 생각하였다.

 

브루트 포스 과정을 설명하면,

1. seq와 cnt 리스트를 만든다. seq는 수열을, cnt는 현재까지 사용한 i의 개수를 의미한다.

2. DFS로 seq를 처음부터 채워나간다. 이때 sum(cnt)가 N을 넘거나 cnt가 seq값보다 더 커지면 return한다.

3. now=N일 때, 개수를 +1 해준다.

 

이렇게 해봤을 때 풀이는 시간초과가 나왔다.

 

그런데 1~30까지 돌려본 결과 1~6까지는 결과가 0,0,0,2,1,0으로 나왔다. 그런데 나머지 숫자 7~30까지는 전부 1이 나왔다.

그래서 "설마 이거 나머지 숫자는 전부 1인건가?" 해서 위와 같이 N이 10 이하일때는 브루트 포스를, 아닐때는 1을 출력했더니 정답이 되었다.

 

알고보니 N>6인 경우에 대해서 self representing seq는 유일한 수열을 갖는다고 한다.

따라서 다음과 같은 코드도 통과 가능하다.

for _ in range(int(input())):
  N = int(input())
  print(int(int(N!=1 and N!=2 and N!=3 and N!=6)+int(N==4)))