[알고리즘] 순열 추측하기 (DFS)

(문제) 순열 추측하기 (DFS)

---

가장 윗줄에 1부터 N까지의 숫자가 한 개씩 적혀 있다.

그리고 둘째 줄부터 차례대로 파스칼의 삼각형처럼 위의 두개를 더한 값이 저장되게 된다.

예를 들어 N이 4 이고 가장 윗 줄에 3 1 2 4 가 있다고 했을 때, 다음과 같은 삼각형이 그려진다.

3  1  2  4
4  3  6
7  9
16

N과 가장 밑에 있는 숫자가 주어져 있을 때 가장 윗줄에 있는 숫자를 구하는 프로그램을 작성하시오.

단, 답이 여러가지가 나오는 경우에는 사전순으로 가장 앞에 오는 것을 출력하여야 한다.

입력설명

첫째 줄에 두개의 정수 N(1≤N≤10)과 F가 주어진다.

N은 가장 윗줄에 있는 숫자의 개수를 의미하며 F는 가장 밑에 줄에 있는 수로 1,000,000 이하이다.

출력설명

첫째 줄에 삼각형에서 가장 위에 들어갈 N개의 숫자를 빈 칸을 사이에 두고 출력한다.

답이 존재하지 않는 경우는 입력으로 주어지지 않는다.

테스트케이스

입력예제	출력예제
4 16	3 1 2 4
5 39	4 1 3 2 5
9 1610	1 2 3 5 9 6 8 4 7
9 730	7 6 4 2 1 3 5 8 9
7 288	1 2 4 5 6 3 7
10 2196	1 6 9 4 2 3 5 10 7 8

---

해결방법

1. 입력이 된다면 1~n 까지 나열 되어있는 것이다.
2. 각각을 더한다. 그러면 하나의 숫자가 된다.
3. 그러면 또 그들을 더하면 하나의 숫자가 된다.
4. 이 반복을 통해서 1개의 출력이 f의 값가 같아지는 것이다.

전부 다 해보는 방법 밖에 없다.

순열 구하는 방법
dfs 순열 구하는 방법

순열들

• 경우 1 : 1 2 3 4
• 경우 2 : 1 2 4 3
• 경우 3 : 1 3 2 4 …

이런 것을 반복한다.

4!의 가지수 -> 24가지를 다 해본다.

각각 더한 값이 16이 발견되면 stop 하고 그 순열을 출력한다.

하지만 이런 식으로 각각 더해서 값을 얻으려고 하는 경우 시간이 오래 걸린다.

그래서 각각으로 더할 경우, 다르게 생각을 해보면 이렇게 된다.

1 2 3 4
1+2, 2+3, 3+4
1+2+2+3, 2+3+3+4
1+2+2+2+3+3+3+4 –> 1이 1개 / 2가 3개 / 3이 3개 / 4가 1개

한번 보면 뭔가 규칙이 보인다.

규칙은 파스칼 삼각형 이항 계수 규칙이다.

파스칼 삼각형이란?

이런식으로 만들어 진다.

해당 n개를 기준으로 n-1에 해당하는 이항 계수가 들어있는 리스트를 생성한다.

생성 후, 만들어진 순열을 각각 곱해서 f의 값과 같아지는 것 만나면 재귀를 끝낸다.

코드

def dfs(x, _sum):
    if x == n and _sum == f:
        # 계수 나오도록
        print(*ch)
        sys.exit(1)
    else:
        for i in range(1, n+1):
            if not i in ch:
                ch.append(i)
                dfs(x+1, _sum + (ch[x]*b[x]))
                ch.pop()

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

b = [1] * n
# 파스칼 삼각형 이항 계수 규칙 조합 이용
for i in range(1, n):
    b[i] = b[i-1] * (n-i) // i

ch = []

dfs(0, 0)