문제
가장 윗줄에 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,sum):
if L==n and sum==m:
for k in res:
print(k,end=' ')
print()
sys.exit(0)
else:
for j in range(1,n+1):
if ch[j]==0:
ch[j]=1
res[L]=j
DFS(L+1,sum+b[L]*res[L])
ch[j]=0
if __name__=="__main__":
n,m=map(int,input().split())
res=[0]*n
b=[1]*(n+1)
for i in range(1,n):
b[i]=b[i-1]*(n-i)//i
ch=[0]*(n+1)
DFS(0,0)
- 조합으로 생각을 하면 n=4이면 위의 이미지와 같이 4가 1번,3이 3번,2가 3번,1이 1번 계산된다.
따라서 n의 계산에 해당하는 배열 b을 생성- 1부턴 n까지의 모든 수의 배열(팩토리얼)들의 파스칼 삼각형을 구현하고 DFS의 중단 조건을 DFS의 레벨이 n과 동일할 때 and 합계가 m값과 같을 때를 조건으로 한다.
3.DFS중 들렸던 노드는 ch배열로 체크해주고 DFS가 끝나면 ch=0을 통해 배열을 다시 초기화한다.
