[김태원 알고리즘] 수열 추측하기 (DFS + 🌟이항계수 구하기)

사용 언어: Python3

문제

이 문제는 순열 구하기(N개 중 N개 뽑기) + 파스칼의 삼각형 계산 문제이다.
순열은 어쩔 수 없이 하나하나 모두 구해야 하지만,
파스칼의 삼각형 계산은 이항계수를 이용해 간단하게 구할 수 있다.

이항계수

이항계수 구하기

N = 4 # N은 파스칼의 삼각형 맨 윗 줄의 원소 수
bc = [1] * N
for i in range(1, N):
    bc[i] = bc[i-1] * (N-i) // i # ✅ 이항계수 초기화

풀이

내 풀이

# 파스칼의 삼각형 계산 (lst의 원소들을 두 개씩 더했을 때 맨 마지막 값 계산)
def calcPascal(lst):
    tot = 0
    for i in range(N):
        tot += lst[i] * bc[i]
    return tot

# 1부터 N까지 중 N개 뽑기 (순열)
def DFS(L):
    if L == N:
        if calcPascal(res) == F:
            ans.append(res[::]) # res 넣으면 안됨
    else:
        for i in range(1, N+1):
            if used[i] == 1:
                continue
            used[i] = 1
            res[L] = i
            DFS(L+1)
            used[i] = 0

N, F = map(int, input().split())

bc = [1] * N # binomial coefficient(이항계수)
for i in range(1, N-1):
    bc[i] = bc[i-1] * (N-i) // i

res = [0] * N # 순열
used = [0] * (N+1) # 순열에 사용한 원소 표시
ans = [] # 가능한 res(수열)들을 담아둘 변수

DFS(0)

print(' '.join(map(str, ans[0])))

다른 풀이

def DFS(L, pSum): # pSum: 부분합
    global isExist
    if isExist:
        return
    if L == N and pSum == F:
        print(' '.join(map(str, res))) 
        isExist = True # ✅ 최초로 발견된 것만 출력하기 위해
    else:
        for i in range(1, N+1):
            if used[i] == 1:
                continue
            used[i] = 1
            res[L] = i
            DFS(L+1, pSum+(res[L]*bc[L])) # ✅ 부분합 누적
            used[i] = 0

N, F = map(int, input().split())

bc = [1] * N # ✅ binomial coefficient(이항계수)
for i in range(1, N-1):
    bc[i] = bc[i-1] * (N-i) // i # ✅ 이항계수 초기화

res = [0] * N # 순열
used = [0] * (N+1) # 순열에 사용한 원소 표시

isExist = False
DFS(0, 0)

• 파스칼의 삼각형 -> 🌟 “이항계수”를 이용하여 계산하는 방법 알아두기!

내 풀이 - 5/4 추가

# N개 중 N개 뽑기
def DFS(L):
    global isExist
    if isExist:
        return
    if L == N:
        tot = 0
        for i in range(N):
            tot += bc[i] * res[i] # ✅ 이항계수를 이용해 파스칼의 삼각형 계산
        if tot == F:
            print(' '.join(map(str, res)))
            isExist = True
    else:
        for i in range(1, N+1):
            if used[i] == 1:
                continue
            res[L] = i
            used[i] = 1
            DFS(L+1)
            used[i] = 0

N, F = map(int, input().split())

bc = [1] * N
for i in range(1, N):
    bc[i] = bc[i-1] * (N-i) // i # ✅ 이항계수 초기화

res = [0] * N
used = [0] * (N+1)

isExist = False
DFS(0)

내 풀이 - 6/19 추가

import sys
sys.setrecursionlimit(10**6)

# 1부터 N까지 N개 뽑기
def DFS(L, pSum): # pSum은 부분합
    global isDone
    if isDone: # 이미 출력을 완료했다면 cut edge
        return
    if L == N:
        if pSum == F:
            print(' '.join(map(str, res)))
            isDone = True
        return
    for i in range(1, N+1):
        if visited[i]:
            continue
        visited[i] = 1
        res[L] = i
        DFS(L+1, pSum + bc[L] * res[L])
        visited[i] = 0

N, F = map(int, input().split())
isDone = False

# 이항계수 구하기
bc = [1] * N
for i in range(1, N):
    bc[i] = bc[i-1] * (N-i) // i

res = [0] * N
visited = [0] * (N+1)
DFS(0, 0)

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기