섹션 6. 수열 추측하기

---

순열라이브러리와 DP를 통해 이항계수를 구한 풀이법

from itertools import permutations

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

tri = [[1] * 11 for _ in range(11)]
tri[2][1] = 2
cnt = 0
for i in range(3, 11):
    for j in range(1, i):
        cnt += 1
        tri[i][j] = tri[i - 1][j - 1] + tri[i - 1][j]

b = tri[n - 1]
b = b[:n]
seq = list(range(1, n + 1))

for v in permutations(seq):
    seq = list(v)
    res = 0
    for i in range(n):
        res += seq[i] * b[i]

    if res == f:
        print(*seq)
        break

 

DFS를 이용한 풀이

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


def dfs(l, sum):
    if l == n and sum == f:
        print(*p)
        exit()

    for i in range(1, n + 1):
        if not ch[i]:
            ch[i] = 1
            p[l] = i
            dfs(l + 1, sum + (p[l] * b[l]))
            ch[i] = 0


p = [0] * n
b = [1] * n

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

ch = [0] * (n + 1)

dfs(0,0)

가장 밑의 줄에 있는 수 F는 구해야 하는 수열에서 이항계수만큼 곱해야 구할 수 있다는 것을 알아채야 풀 수 있는 문제였다. 

문제에서 주어진 예시를 보자. 구해야 하는 수열은 3 1 2 4 인데 F=16은 \(3 * 1 + 1 * 3 + 2 * 3 + 4 * 1 \)의 결과값으로 수열에 곱한 계수는 각각 \( {}_3 C_0 \\~\\ {}_3 C_1 \\~\\ {}_3 C_2 \\~\\ {}_3 C_3 \\~\\\)과 같다. 즉,  N-1일 때의 이항계수와 같다.

 

따라서 n이 주어지면 n에 해당하는 이항계수 리스트를 만들어서 F와 같은 값이 나올 때까지 모든 수열의 경우의 수와 곱하는 게 핵심 로직이 되겠다.

 

앞으로 파스칼의 삼각형을 이용한 문제(두개를 더한 값 이용)가 나오면 이항계수로 풀 수 있는 지 생각해보자