[인프런] 수열 추측하기

---

문제설명

가장 윗줄에 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개의 숫자를 빈 칸을 사이에 두고 출력한다. 답이 존재하지 않는 경우는 입력으로 주어지지 않는다.

사고과정

• 가장 첫줄에 주어질 수열(1~N 숫자 중 한번씩 써서)을 구해야 하므로 중복을 허용하지 않는 순열을 DFS 탐색으로 모든 경우를 완전탐색한다.
• 그리고 하나의 순열을 탐색하면서 문제에서 주어진 원리에 따라 가장 마지막에 있는 값을 계산해야 한다. 처음에 나는 이것을 for 문과 loop로 계산해 구현하긴 했는데, 테스트 케이스에서 1개 답이 틀려서 낑낑대고 있었다..
• 풀이를 보니, 마지막에 있는 값을 계산하는 것에서 시간 복잡도를 줄여야 했다. 일종의 규칙을 발견하는 것이였는데, 이항계수 규칙을 파악한 후 N 값에 따라 정확히는 N 길이에 따라 이항계수 리스트를 미리 초기화 해놓고 탐색한 순열과 동일한 인덱스끼리 값을 곱한 후 더해서 계산하면 시간 복잡도가 많이 준다. 
• 설명만 듣고 직접 풀이를 해보았는데, 잘 구현은 했지만 강사님 풀이와 비교해보니 좀 다른점이 있었다. 우선 이항계수 테이블 초기화할 때, 파이썬으로 조합 계산 식을 구했어야 했는데, 난 math 라이브러리를 사용했지만 강사님은 또 그 조합 계산 식에서도 규칙을 발견해 파이썬으로 구현했다. 또 순열 하나씩 탐색하면서 그 순열의 합도 동시에 누적하면서 탐색했다. 갈 길이 멀다..

풀이(스스로 못 푼 풀이)

- 강사님 풀이(권장!)

# 강의 Solution -> 조합 규칙찾아서 계산, DFS 탐색하면서 경우의 수 합 동시 계산
n, f = map(int, input().split())
p = [0] * n          # 순열 경우의 수
b = [1] * n          # 이항계수 값 -> 맨 처음과 끝은 무조건 1이니깐!
ch = [0] * (n+1)     # 중복허용하지 않으니까 방문체크 테이블
# 이항 계수 n에 맞게 갱신 -> math 라이브러리 사용하지 않고!
for i in range(1, n-1):
    b[i] = b[i-1]*(n-i) // i


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


DFS(0, 0)

- 나의 풀이

n, f = map(int, input().split())
check = [0] * (n+1)
res = [0] * n
binary = [int(factorial(n-1)/(factorial(r)*factorial(n-1-r))) for r in range(0, n)]
flag = False

def dfs(L):
    global flag
    if flag:
        return
    if L == n:
        f_val = 0
        for j in range(0, n):
            f_val += (res[j] * binary[j])
        if f_val == f:
            #print('f_val:', f_val, 'res:', res)
            print(' '.join(list(map(str, res))))
            flag = True
    else:
        for i in range(1, n+1):
            if check[i] == 0:
                check[i] = 1
                res[L] = i
                dfs(L+1)
                check[i] = 0

dfs(0)