수열 추측하기(순열, 파스칼 응용)

인프런 김태원님의 파이썬 알고리즘 문제풀이를 듣고 작성한 글입니다.

https://inf.run/Wa5t

파이썬 알고리즘 문제풀이 (코딩테스트 대비) - 인프런 | 강의

이 문제가 좀 어려웠다..

 

내 풀이

#내 풀이           //테스트 1,4는 통과하는데 나머지는 시간초과
def DFS(L):
    global res
    ch = pascal(n)
    if L == n:
        if len(res) != len(set(res)):
            pass
        else:
            ssum = 0
            for i in range(len(res)):
                ssum += res[i] * ch[i]
            if ssum == f:
                for j in res:
                    print(j, end = ' ')
                sys.exit(0)
    else:
        for i in range(1, n+1):
            res[L] = i
            DFS(L+1)

def factorial(n):
    if n <= 1:
        return 1
    else:
        return n * factorial(n-1)

def pascal(n):
    ch = [0] * n
    for i in range(n):
        ch[i] = int(factorial(n-1)/(factorial(n-1-i) * factorial(i)))
    return ch

if __name__ == "__main__":
    n, f = map(int, input().split())
    res = [0] * n
    DFS(0)

테스트 1, 2, 3, 4, 5 중에 테스트 1, 4는 통과했으나

나머지는 시간초과가 떴다.

내생각엔 아마 factorial과 pascal 함수 부분을 저렇게 재귀함수 식으로 

구현하면 시간초과의 원인이 되는 것 같다.

---

이 문제는 순열의 개념과 약간의 수학적 개념이 필요했다.

아래로 내려가는 값을 구할때 일일히 더해가면서 구하면 시간이 오래 걸리기때문에

n = 4 일때, 각 값은 1 3 3 1 의 횟수를 더하게 된다.

n = 5 일때, 각 값은 1 4 6 4 1 의 횟수를 더하게 된다.

이 값은 이항계수 값과 같다는 것을 알 수 있다.

따라서 순열 배열 p 값에다가 각 이항계수 값을 곱해서 더해주면 된다.

 

강의 풀이

#강의 풀이
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)

p는 순열을 저장하는 배열

b는 이항계수를 저장하는 배열

ch는 수가 사용되었는지 체크하는 배열

 

이항계수 배열을 구하는 부분

처음 for i in range(1, n):

           b[i] = (b[i-1] * (n-i)) // i

이 부분이 생각하기 어려웠다고 생각한다.