[Python Algorithm] 완전탐색(DFS) - 라이브러리를 이용한 순열(순열 추측하기)

> 완전탐색 - 백트랙킹, 상태트리와 CUT EDGE / DFS 기초 

https://sanamode.tistory.com/51 

[Python Algorithm] 완전탐색(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

 

 

import sys
import itertools as it

n, f = map(int, input().split())
b = [1] * n
cnt = 0

for i in range(1,n):
	b[i] = b[i-1]*(n-i)/i
    
a= list(range(1, n+1))
for tmp in it.permutations(a):
	sum = 0
    for L, x in enumerate(tmp):
    	sum += (x*b[L])
    if sum==f:
    	for x in tmp:
        	print(x, end=' ')
        break

 

 

 

⭐️ Point ! ⭐️

• 라이브러리 itertools 사용 !
  for tmp in it.permutations(a):
  ( 1, 2, 3, 4)
  ( 1, 2, 4, 3)
  .... 24개 출력
  
  4개 중에 3를 뽑아 순열을 구하려면 (여기서 4는 예제에서 a의 원소의 개수가 4개)
  for tmp in it.permutations(a, 3): 으로 사용
  
  
• for L, x in enumerate(tmp):
  리스트 a의 원소들에 접근함. 위의 예제 같은 경우
  0 1
  1 2
  2 3
  3 4
  0 1
  1 2
  2 4
  3 3 .... 이런식으로 접근 
  
  
• 위에서 for문안에 L변수가 필요한 이유는 b리스트의 값들을 원소 순서대로 곱해주기 위해서 

 

 

출처

• 인프런 : 파이썬 알고리즘 문제 풀이