9. 수열 추측하기

수열 추측하기

가장 윗줄에 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

 

문제풀이

import sys
sys.stdin=open("input.txt", "r")
def DFS(L, sum):
    
    if L==n and sum ==f: #L은 깊이를 의미함  
        for x in p:
            print(x, end=' ')
        sys.exit(0)
    
        
    else:
        for i in range(1, n+1): #range의 범위는 트리의 가지(자식) 수를 의미한다. i는 branch의 값을 의미한다.  
            if ch[i] ==0:
                ch[i] =1   
                p[L]=i
                DFS(L+1, sum+(p[L]*b[L]))
                ch[i] =0

if __name__=="__main__":
    n, f = map(int, input().split())
    res=[0]*n 
    ch=[0]*(n+1)
    p =[0]*n    #p리스트 길이는 어느 정도의 깊이(레벨)를 의미한다. 
    b =[1]*n
    for i in range(1, n-1):
        b[i]=b[i-1]*(n-i)//i
    DFS(0,0)

 

해설

▶이항정리를 구한다. 

 

▶b리스트(이항정리)의 각각의 값과 p리스트의 각각의 값을 곱해서, 그 합이 f와 같다면, 그때의 p리스트를 출력한다.  

 

▶다만 정답이 여러 개가 나올 경우 사전순서대로 정렬하였을 때 맨 앞에 오는 하나의 리스트만 출력한다.