수열 추측하기(순열)

생성일: 2022년 2월 6일 오후 7:59

구현 코드 ⭐

# 수열 추측하기
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)

• n = 4, k = 16 기준을 예시로 들자면, 모든 가능 한 경우의 순열을 검사해야 하는 것은 맞다. (예를들어 [1,2,3,4], [1,3,2,4], .... , [4,3,1,2])
• 다만, 검사하는 방식에 있어서 위의 순열들을 전부 두개씩 더해가면서 k가 되는지 확인하는 것이 아니고 특정한 규칙이 있다.
• 바로 이항계수이다. n이 4인 기준으로 이항 계수는 [1,3,3,1] 이다. 이 수를 정답인 [3,1,2,4] 에 각각 곱하면 k 값인 16이 나온다.
• 따라서 b 리스트에 주어진 n에 맞는 이항 계수 값들을 저장 한 뒤, 재귀 함수를 돌면서 생기는 모든 순열의 경우의 수를 b 배열과 각각 곱해서 더한 값이 k 와 같다면 정답인 경우인 수 이기 때문에 출력하고 프로그램을 종료한다.