수열 추측하기

문제

수열 추측하기

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

def DFS(L, sum):
    if L==n and sum==f:
        for x in p:
            print(x, end=' ')
        sys.exit(0)
    else:
        for i in range(1,n+1):
            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())
    p=[0]*n #순열 만들기
    b=[1]*n #이항 계수
    ch=[0]*(n+1) #체크 리스트
    for i in range(1,n):
        b[i]=b[i-1]*(n-i)//i
    DFS(0,0)

-리스트 p

순열 만드는 리스트이다. 

1부터 N까지의 숫자가 나열되는 경우를 기입하는 리스트이다.

DFS함수를 돌리면서 모든 경우의 수를 돌린다

 

-리스트 b

이항 계수 리스트이다.

삼각형 가장 위 수열에서 가장 아래 도출값을 구하기 위해서는 이항계수를 구해서 그 순서에 맞게 리스트 p와 곱해서 더해야 한다.

 

-리스트 ch

순열 조합은 중복된 것이 나오면 안되기 때문에 따로 체크 리스트를 만들어서 미연에 방지한다.

if ch[i]==0:

                ch[i]=1

                p[L]=i

DFS 함수 내부의 코드이다. 이를 통해 중복 안된 숫자만 리스트 p에 집어넣는 것을 알 수 있다.

 

-이항계수 리스트 b 

for i in range(1,n):

        b[i]=b[i-1]*(n-i)//i

 

-DFS

def DFS(L, sum):

    if L==n and sum==f:

        for x in p:

            print(x, end=' ')

        sys.exit(0)

    else:

        for i in range(1,n+1):

            if ch[i]==0:

                ch[i]=1

                p[L]=i

                DFS(L+1, sum+(p[L]*b[L]))

                ch[i]=0