[Python] 백준 10220 - Self Representing Seq

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

문제

자연수 N이 주어질 때 다음과 같은 길이 N인 수열 A의 개수를 구하여라

$A_i$ = A에서 i가 등장하는 횟수 (0 ≤ i < N)

입력

입력 파일의 첫 번째 줄에 테스트 케이스의 수를 의미하는 자연수 T가 주어진다. 그 다음에는 T개의 테스트 케이스가 주어진다.

각 테스트 케이스에는 수열의 길이를 의미하는 하나의 자연수 N (1 ≤ N ≤ 100)이 입력으로 주어진다.

출력

각 테스트 케이스마다 한 줄에 가능한 A의 개수를 1,000,000,007로 나눈 나머지를 출력한다.

 

---

풀이

내 백준 인생 처음으로 '찍어서' 맞춘 문제이다.

(물론 증명도 이 글 뒷부분에 할 것이다. 맞추기만 하고 증명을 안하면 뭔가 찜찜하달까.)

 

일단 처음에는 작은 N에 대해서 몇 개를 적어볼 것인데, 여기서 다음의 2가지 관찰을 할 수 있다.

 

1. 수열의 수들의 합은 N이다.

2. 수열의 수와 각 인덱스들의 곱의 합은 N이다.

 

이것의 증명은 쉽기때문에 안할 것이다.

 

어쨌든 이 두 가지를 가지고 작은 N에 대해서 조건을 만족하는 수열을 조금 찾아보면, 다음과 같다.

 

N = 1: 없음

N = 2: 없음

N = 3: 없음

N = 4: 2개

N = 5: 1개

 

이 다음부터는 코드를 짜서 조건을 만족하는 수열을 찾아보았다. (N = 9일때까지 돌렸는데, 돌리는데 5분 걸렸다.)

분명 더 효율적인 방법이 있을것이다....근데 귀찮아서

N=9

 

N = 6: 없음

N = 7: 1개

N = 8: 1개

N = 9: 1개

 

여기서 주목해볼 것은 N = 7, 8, 9일때의 해인데, 각각 다음과 같다.

[3, 2, 1, 1, 0, 0, 0]

[4, 2, 1, 0, 1, 0, 0, 0]

[5, 2, 1, 0, 0, 1, 0, 0, 0]

 

뭔가 규칙이 있지 않은가...?

 

여기서 레전드 찍신이 발동해서

N이 7 이상일때는 해가 1개가 아닐까?

 

tmp = [0] + [0, 0, 0, 2, 1, 0, 1, 1] + [1]*100
T = int(input())
for i in range(T):
    N = int(input())
    print(tmp[N])

그리고 코드를 제출해보았는데...

 

말도 안돼. 아예 개꿀 플레3문제라니.

 

좋다. 증명을 안하면 찝찝하니

N이 7 이상일 때는 저 꼴의 해로, 답이 유일함을 증명해보겠다.

이를 위해서 우리는 위에서 말한 2가지 관찰을 이용할 것이다.

 

0의 개수를 기준으로 카운팅해줄건데, 

큰 것부터 해보자.

일단 0이 N일때는 말이 안된다.

0이 N-1일때는 숫자 N-1의 개수가 0개로 표시되어있어서 모순, 말이 안된다.

0이 N-2일때는 N-2의 개수가 최소 1개, 즉 1의 자리에 무언가 표시되어있어야 하는데 0이어서 모순. 

0이 N-3일때는 N-3의 자리는 1로 채우고, 1의 자리는 2로 채우고(1은 안된다), 2의 자리를 채우려고 보면 0의 개수가 부족해서 모순.

0이 N-4일때 해가 나온다. [N-4, 2, 1, 0, 0, 0, ..... 1, 0, 0, 0]의꼴이다.

 

0이 이거보다 더 작을때는 어떨까?

결론부터 말하자면 수열의 수와 각 인덱스들의 곱의 합은 N이다. 라는 관찰에 모순된다.

왜냐? 이 곱의 합이 N보다 커지는 것을 막기 위해서 0을 최대한 뒤쪽에 배치한다고 하고,

첫 번째 관찰인 수열의 수들의 합은 N이다. 에 맞춰서 나머지 수들을 아무리 적게 배치해봐도

곱의 합이 N을 넘어가게 된다.

 

 

따라서 해는 0이 N-4개 있을 때, 1개로 존재한다.

 

이 논리를 N = 10일때 그림으로 그려보면 다음과 같다.

 

그래서 위와 같은 코드가 성립한다.