[Python-CodingTest] 6-9. 수열 추측하기 (순열,파스칼 응용)

수열 추측하기

문제 정리

입력

4 16

처리 과정

1. 파스칼의 삼각형의 마지막 값을 구하기 위해서는 처음 입력된 숫자 리스트(=res)와 이항계수(=coef) 값을 일대일 곱셈하는 것이다.
2. 이항계수의 값을 구하는 방법은 조합을 이용한다. (n=4라면 이항계수는 [1(=3C0),3(=3C1),3(=3C2),1(=3C3)])
3. 조합(nCr)을 계산하는 방법은 coef의 이전 값에 n-i를 곱하고 i로 나눈다.
   또는 n!/(n-r)!r! 공식을 이용한다.
4. DFS()는 순열과 비슷하게 작성한다. 차이점은 sum을 누적하며 주어진 f와 같은지 확인한다.
   이때 sum에는 res 값과 coef(이항계수) 값을 일대일로 곱한 값을 누적한다.

출력

3 1 2 4

내 답

import sys
sys.stdin = open("./input/in9.txt", "rt")

def DFS(L):
    if L==n:
        sum=0
        for i in range(n):
            sum+=res[i]*coef[i] # res 값과 coef(이항계수) 값을 일대일 곱셈 계산
        if sum==f: # f와 같다면 해당 res가 찾고자하는 res
            for x in res:
                print(x,end=' ')
            print()
            sys.exit(0) # 최초로 발견된 res 출력 후 프로그램 종료
    else: # 순열과 마찬가지로 구성
        for i in range(1,n+1):
            if ch[i]==0: # 체크리스트의 값이 0일때만 순열(=res) 만들기
                ch[i]=1
                res[L]=i

                DFS(L+1)
                ch[i]=0 # back을 한 뒤에는 체크리스트 되돌리기

def comb(n,r): # 조합(combination): nCr
    if r>n//2:
        r=n-r # 4C3==4C1
    res=fact(n)/(fact(n-r)*fact(r)) # 조합 계산식
    return int(res)

def fact(n): # 팩토리얼(factorial): n!
    res=1
    for i in range(1,n+1):
        res*=i
    return res

if __name__=="__main__":
    n,f=map(int,input().split())
    res=[0]*n # res에 모든 조합을 다 해보기

    ch=[0]*(n+1) # 중복을 허락하지 않는 체크리스트 (인덱스 번호와 동일)

    coef=[0]*n # 이항계수 (binomial coefficient)
    for i in range(n):
        coef[i]=comb(n-1,i) # n=4라면 이항계수 [1(=3C0),3(=3C1),3(=3C2),1(=3C3)]

    DFS(0)

풀이

import sys
sys.stdin = open("./input/in9.txt", "rt")

def DFS(L,sum): # sum은 f를 향해가는 누적값
    if L==n and sum==f:
        for x in res:
            print(x,end=' ')
        print()
        sys.exit(0) # 최초로 발견된 res 출력 후 프로그램 종료
    else:
        for i in range(1,n+1):
            if ch[i]==0:
                ch[i]=1
                res[L]=i

                DFS(L+1,sum+(res[L]*coef[L])) # sum에 res와 coef(이항계수)를 일대일로 곱한 값 누적
                ch[i]=0


if __name__=="__main__":
    n,f=map(int,input().split())
    res=[0]*n # res에 모든 조합을 다 해보기

    ch=[0]*(n+1) # 중복을 허락하지 않는 체크리스트 (인덱스 번호와 동일)

    coef=[1]*n # 이항계수 (binomial coefficient) # 이항계수의 양 끝은 무조건 1
    for i in range(1,n): # n=4라면 이항계수 [1(=3C0),3(=3C1),3(=3C2),1(=3C3)]
        coef[i]=coef[i-1]*(n-i)//i

    DFS(0,0)

정리

• 파스칼의 삼각형의 마지막 값을 구하기 위해서는 처음 입력된 숫자 리스트(=res)와 이항계수(=coef) 값을 일대일로 곱한다.
• 이항계수의 값을 구하는 방법은 조합을 이용한다.
  (n=4라면 이항계수는 [1(=3C0),3(=3C1),3(=3C2),1(=3C3)])
• 조합(nCr)을 계산하는 방법은 coef의 이전 값에 n-i를 곱하고 i로 나눈다.
  또는 n!/(n-r)!r! 공식을 이용한다.

---

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

맨 위로 이동하기