051 - 수열 추측하기

가장 윗줄에 1부터 N까지의 숫자가 한 개씩 적혀 있다. 그리고 둘째 줄부터 차례대로 파스칼 의 삼각형처럼 위의 두개를 더한 값이 저장되게 된다. 예를 들어 N이 4 이고 가장 윗 줄에 3 1 2 4 가 있다고 했을 때, 다음과 같은 삼각형이 그려진다.

 

 

 

N과 가장 밑에 있는 숫자가 주어져 있을 때 가장 윗줄에 있는 숫자를 구하는 프로그램을 작성하 시오. 단, 답이 여러가지가 나오는 경우에는 사전순으로 가장 앞에 오는 것을 출력하여야 한다.

 

 

▣ 입력설명
첫째 줄에 두개의 정수 N(1≤N≤10)과 F가 주어진다. N은 가장 윗줄에 있는 숫자의 개수를 의 미하며 F는 가장 밑에 줄에 있는 수로 1,000,000 이하이다.

 

▣ 출력설명
첫째 줄에 삼각형에서 가장 위에 들어갈 N개의 숫자를 빈 칸을 사이에 두고 출력한다. 답이 존재 하지 않는 경우는 입력으로 주어지지 않는다.

 

▣ 입력예제 1

4 16

 

▣ 출력예제 1

3 1 2 4

 

 

 

• 함수의 효율성을 비교하기 위해서 실행시간을 출력하는 코드를 추가함

import time
#import sys
#sys.stdin = open('in.txt', 'rt')


def DFS(L):
    global res

    if res == 1:
        return
    if L == n:
        sum = 0
        for j in range(n):
            sum += a[j]*c[j]
        if sum == f:
            print(*a)
            res = 1
            return
    else:
        for i in range(n):
            if ch[i] == 0:
                ch[i] = 1
                a[L] = i+1
                DFS(L+1)
                ch[i] = 0


def DFS2(L, sum):
    global res

    if res == 1:
        return
    if L == n:
        if sum == f:
            print(*a)
            res = 1
            return
    else:
        for i in range(1, n+1):
            if ch[i] == 0:
                ch[i] = 1
                a[L] = i
                # print('DFS2:b ch:{}, i:{}, L:{},{},{}'.format(
                #     ch, i, L, a[L], a))
                DFS2(L+1, sum+a[L]*c[L])
                ch[i] = 0
                a[L] = 0  # 스택 디버깅 검증을 위해서 추가함. 해당 레벨이 종료됨을 의미.
                # print('DFS2:a ch:{}, i:{}, L:{},{},{}'.format(
                #     ch, i, L, a[L], a))


if __name__ == '__main__':
    n, f = map(int, input().split())
    a = [0]*n
    c = [1]*n
    ch = [0]*(n+1)
    res = 0
    for i in range(1, n):
        c[i] = int(c[i-1]*(n-i)/i)

    start = time.time()
    DFS(0)
    end = time.time()
    print('DFS1 {:.6f}'.format(end-start))
    res = 0
    start = time.time()
    DFS2(0, 0)
    end = time.time()
    print('DFS2 {:.6f}'.format(end-start))

 

 

 

• sum 을 바로 계산하는 함수가 효율적임

 ~python aa.py
3 1 2 4
DFS1 0.000057
3 1 2 4
DFS2 0.000032

 

 

 

• 라이브러리를 사용한 코딩 샘플

import itertools as it
#import sys
#sys.stdin = open('in.txt', 'rt')

if __name__ == '__main__':
    n, f = map(int, input().split())
    a = [i for i in range(1, n+1)]
    c = [1]*n
    for i in range(1, n):
        c[i] = int(c[i-1]*(n-i)/i)

    print(n, f, a, c)

    for i, x in enumerate(it.permutations(a)):
        sum = 0
        for j in range(n):
            sum += x[j]*c[j]
        if sum == f:
            print(*x)
            break

 

 

 

 

컴비네이션(combination) 개념 :

https://ko.wikipedia.org/wiki/%EC%A1%B0%ED%95%A9

조합 - 위키백과, 우리 모두의 백과사전

 

 

 

순열 개념:

https://ko.wikipedia.org/wiki/%EC%88%9C%EC%97%B4

순열 - 위키백과, 우리 모두의 백과사전