[파이썬 알고리즘 문제풀이 입문] 완전탐색 (백트랙킹, 상태트리와 CUT EDGE) / DFS(깊이우선탐색) 기초 - 수열 추측하기 (DFS)

*문제 본문은 강의 내용과 관련되어 있어 자세하게 적지 않았습니다.

 

 

 

문제

가장 윗줄에 1부터 N까지의 숫자가 한 개씩 적혀 있다. 그리고 둘째 줄부터 차례대로 파스칼의 삼각형처럼 위의 두 개를 더한 값이 저장되게 된다.
N과 가장 밑에 있는 숫자가 주어져 있을 때 가장 윗줄에 있는 숫자를 구하는 프로그램을 작성하시오.
(단, 답이 여러가지가 나오는 경우에는 사전 순으로 가장 앞에 오는 것을 출력하여야 한다.)

 

 

 

풀이

• 답안 : Python

import sys
input = sys.stdin.readline

def DFS(index, sum):
    if index == N and sum == F:
        for i in p:
            print(i, end=' ')
        sys.exit(0) # 만족하는 것이 여러가지 있지만 그 중 첫 번째 것만 출력
    else:
        # 순열 만들기
        for i in range(1, N+1):
            if visited[i] == 0:
                visited[i] = 1
                p[index] = i
                
                # index는 1씩 증가 / sum은 구한 순열의 값과 구한 이항계수끼리 곱해줘서 누적합
                DFS(index+1, sum+(p[index]*b[index]))
                
                visited[i] = 0

N, F = map(int, input().split())
b = [1] * N # 이항계수
p = [0] * N # 순열
visited = [0] * (N+1) # 중복방지

# 이항 계수 N에 따라서 설정
for i in range(1, N):
    b[i] = (b[i-1] * (N-i)) // i

DFS(0, 0)

- 제일 어려웠던 부분이 이항 계수 구할 때 규칙 찾는 것이었다. 답안을 보고 규칙에 대해서 이해할 수 있었다.

    → 분자 : (이전 값) x ((N-1)에서 하나씩 감소)

    → 분모 : 1 x (N-1)까지 1씩 증가하면서  (for문에 의해서 i가 1씩 증가된다.)

- DFS(index+1, sum+(p[index]*b[index])) : p에 있는 값과 b에 있는 이항 계수를 각각 곱하여 누적합을 구한다.

- 나머지 로직은 이전 문제인 '순열 구하기'와 똑같다.

- 답이 여러가지 나왔을 때 한 가지의 답만 출력해야 하기 때문에, 한 가지 답만 출력하고 강제로 종료시켜 준다.

 

 

cf.) 라이브러리 사용한 답안

import sys
from itertools import permutations
input = sys.stdin.readline

N, F = map(int, input().split())
b = [1] * N

for i in range(1, N):
    b[i] = (b[i-1] * (N-i)) // i

a = list(range(1, N+1))
for p in permutations(a):
    sum = 0
    
    for idx, element in enumerate(p):
        sum += (element*b[idx])
        
    if sum == F:
        for element in p:
            print(element, end=' ')
        break

- 코딩테스트에서 라이브러리 사용을 제한하는 경우도 있기 때문에, 너무 라이브러리에 의존X