수열 추측하기

가장 윗줄에 1부터 N까지의 숫자가 한 개씩 적혀 있다. 그리고 둘째 줄부터 차례대로 파스칼
의 삼각형처럼 위의 두개를 더한 값이 저장되게 된다. 예를 들어 N이 4 이고 가장 윗 줄에 3
1 2 4 가 있다고 했을 때, 다음과 같은 삼각형이 그려진다.

	3 1 2 4
	 4 3 6
	  7 9
	   16

N과 가장 밑에 있는 숫자가 주어져 있을 때 가장 윗줄에 있는 숫자를 구하는 프로그램을 작성하
시오. 단, 답이 여러가지가 나오는 경우에는 사전순으로 가장 앞에 오는 것을 출력하여야 한다.

▣ 입력설명

첫째 줄에 두개의 정수 N(1≤N≤10)과 F가 주어진다. N은 가장 윗줄에 있는 숫자의 개수를 의
미하며 F는 가장 밑에 줄에 있는 수로 1,000,000 이하이다.

▣ 출력설명

첫째 줄에 삼각형에서 가장 위에 들어갈 N개의 숫자를 빈 칸을 사이에 두고 출력한다. 답이 존재
하지 않는 경우는 입력으로 주어지지 않는다.

▣ 입력예제 1

4 16

▣ 출력예제 1

3 1 2 4

풀이

• 결과 값을 모두 알기 위해 순열을 사용했습니다.
• 파스칼의 삼각형으로 이항계수를 사용하면 좋습니다.

처음 푼 풀이

def solution(a):
    while len(a) > 1:
        b = list()
        for i in range(len(a) - 1):
            b.append(a[i] + a[i + 1])
        a = b.copy()
    return a[0]
    
    
n, f = map(int, input().split())
lst = [i for i in range(1, n + 1)]
for item in list(permutations(lst, n)):
    res = solution(list(item), b)
    if res == f:
        item = list(map(str, item))
        print(" ".join(item))
        break

• 이 부분의 문제가 뭐냐면, solution에서의 시간 복잡도가 너무 많이 들어갑니다.

	3 1 2 4
	 4 3 6
	  7 9
	   16

• 위의 삼각형을 모두 더하는 과정이 solution인데 리스트를 순열을 사용하는 것 자체도 시간복잡도가 O(n!)이기 때문에 전체적인 시간복잡도가 많이 들어갑니다.
• 여기서 해결책은 바로 이항 계수입니다.
  
• 위와 같은 다항식의 계수들로 표현되는 것이 이항 계수입니다.

	3 1 2 4
	 4 3 6
	  7 9
	   16

• 여기 파스칼의 삼각형에서 맨 마지막 줄의 16은 3+1+1+1+2+2+2+4입니다.
  즉, 3이 한 번, 1이 세 번, 2가 세 번, 4이 한 번 더해지는 구조입니다.
  다시 한번 이항 계수로 써보면 3C0 + 3C1 + 3C2 + 3C3입니다.

• 위와 같이 solution을 작성하는 것보다 아래와 같이 이항계수를 사용해서 하는 것이 좋습니다.

def solution(a, mul):
    for i in range(n):
        a[i] *= mul[i]
    return sum(a)
    
    
n, f = map(int, input().split())
lst = [i for i in range(1, n + 1)]

b = [1] * n
# 이항계수 구하기
for i in range(1, n - 1):
    b[i] = b[i-1] * (n - i) // i
for item in list(permutations(lst, n)):
    res = solution(list(item), b)
    if res == f:
        item = list(map(str, item))
        print(" ".join(item))
        break