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)))