Algorithm - 수열 추측하기(순열, 파스칼 삼각형 활용)

 

알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다.
개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다.

 

문제

[수열 추측하기(순열, 파스칼 삼각형 활용)]

 

가장 첫 번째 줄에 1부터  N까지의 숫자가 한 개씩 적혀 있다. 그리고 두 번째 줄부터 차례대로 파스칼의 삼각형의 원리로 위의 두 개를 더한 값이 저장되어 진행된다. 

 

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

 

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

단, 답이 여러 개 나오는 경우에는 사전 순으로 가장 앞에 오는 답을 출력하시오.

 

 

 *입력 설명

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

N은 가장 윗줄에 있는 수열의 길이를 의미하며, F는 가장 밑에 있는 수를 의미한다.

 

*출력 설명

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

 

 

---

 

 

풀이(Python)

답안(1)

import sys
sys.stdin = open('AA/input_51.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)
    
# 출력 : 3 1 2 4

 

답안(2) : 라이브러리 활용

import sys
import itertools as it
sys.stdin = open('AA/input_51.txt', 'rt')

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

# 출력 : 3 1 2 4

 

input_51.txt(입력)

4 16

 

 

중요내용

1. 파스칼 삼각형의 가장 밑에 있는 값은 원수열의 각 항과 파스칼 삼각형으로 만들어진 원수열 계수의 곱으로 도출된다.
2. 즉, N = 4이고 원수열이 1, 2, 3, 4라고 하면 파스칼 삼각형의 가장 밑에 있는 값은 3C0 * 1 + 3C1 * 2 + 3C2 * 3 + 3C3 * 4으로 20이 된다.
3. 여기서 파스칼 삼각형으로 만들어진 원수열의 계수는 n-1C0, n-1C1, ... , n-1Cn-2, n-1Cn-1 의 규칙을 가진다. 
4. 따라서 원수열의 경우의 수를 모두 찾아서 미리 저장해둔 원수열의 계수(파스칼 삼각형 계수)에 적용(곱하기)하면서 원하는 값(파스칼 삼각형의 가장 밑에 값)이 나올 때까지 반복 실행하면 된다.
5. 변수 p는 원수열의 모든 경우의 수를 저장하는 변수이다.
6. 변수 b는 파스칼 삼각형의 계수(원수열의 계수)를 모두 저장하는 변수이다.
7. 변수 ch는 수열을 만들 때, 중복을 방지하기 위해 사용하는 변수이다.
8. 파스칼 계수를 구할 때에는 바로 앞 항을 사용하여 구한다. (구체적인 원리는 코드 참조)
9. 변수 sum은 파스칼 삼각형의 가장 밑에 있는 값을 저장하는 변수이다.
10. sys.exit(0)는 가장 먼저 나온 결과 값만을 출력하고 해당 프로그램을 중지시키기 위한 코드이다.
11. 재귀함수와 스택 자료구조를 활용한 답안이다.
12. itertools 라이브러리의 permutations() 함수는 인자로 들어온 값들을 가지고 만들 수 있는 모든 순열의 결과를 보여준다.
13. 참고로, permutations() 함수의 두 번째 인자를 사용하면 첫 번째 인자로 들어온 값들 중에서 두 번째 인자의 개수 만큼을 뽑아서 순열을 만들어준다. (ex. permutations(list, k))
14. 라이브러리를 활용한 답안(2)의 문제접근 방식도 답안(1)의 방식과 동일하다.