[DFS기초 ] 수열추측하기(파스칼 삼각형,순열)

수열추측하기(파스칼 삼각형,순열)

 

가장 윗줄에 1부터 N까지의 숫자가 한 개씩 적혀 있다.

그리고 둘째 줄부터 차례대로 파스칼 의 삼각형처럼 위의 두개를 더한 값이 저장되게 된다.

예를 들어 N이 4 이고 가장 윗 줄에 3 1 2 4 가 있다고 했을 때, 다음과 같은 삼각형이 그려진다.

 

 

 

N과 가장 밑에 있는 숫자가 주어져 있을 때 가장 윗줄에 있는 숫자를 구하는 프로그램을 작성하 시오.

단, 답이 여러가지가 나오는 경우에는 사전순으로 가장 앞에 오는 것을 출력하여야 한다.

 

▣ 입력설명
첫째 줄에 두개의 정수 N(1≤N≤10)과 F가 주어진다.

N은 가장 윗줄에 있는 숫자의 개수를 의 미하며 F는 가장 밑에 줄에 있는 수로 1,000,000 이하이다.

▣ 출력설명
첫째 줄에 삼각형에서 가장 위에 들어갈 N개의 숫자를 빈 칸을 사이에 두고 출력한다.

답이 존재 하지 않는 경우는 입력으로 주어지지 않는다.

 

▣ 입력예제 1

4 16

▣ 출력예제 1

3 1 2 4 

 

 

 

 

 

나의 코드

def DFS(L):
    if L==n:
        S=0
        for i in range(n):
            
            S=S+(res[i]*arr1[i])
        if S==m:
            print(res)
    else:
        for i in range(1,n+1):
            if ch[i]==0:
                ch[i]=1
                res[L]=i
                DFS(L+1)
                ch[i]=0

n,m=map(int,input().split())

res=[0]*n
ch=[0]*(n+1)


arr1=[0]*n
arr1[0]=1
arr1[n-1]=1
for i in range(1,n):
    arr1[i]=arr1[i-1]*(n-i)//i

DFS(0)

 

기본적으로 순열로 가능한 모든 조합을 찾는다.

순열의 조합을 저장할 res와 해당 값이 이미 저장되어있는지 체크하기위한 ch.

위와 같이 문제에서 파스칼 삼각형의 합을 추측하다보니 위와같은 규칙이 있다.

arr1[0]=1
arr1[n-1]=1
for i in range(1,n):
    arr1[i]=arr1[i-1]*(n-i)//i

 

위와 같은 점화식으로 해당 숫자들을 저장.

기본적으로 양옆은 모두 1이며 이후 사이값들은 이전 저장된 값 *(n-i(해당 저장인덱스))//i(해당인덱스)로 구할수 있다.

 

 

 

 

import sys
sys.stdin=open("input.txt", "rt")
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)

크 정답 코드와 거의 일치한다.

DFS의 인자로 합을 가진채 탑색을 하고 있고 나의 코드는 모든 순열 조합을 구한뒤 합을 구했다.

 

정답 코드가 시간복잡도 측면에서 불필요한 값들을 L==n인 시점에서 추가적으로 탐색을 안해서 조금 더 좋은것 같다.