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

1 2 3 4 가 일렬로 나열되어 있을 때 하나씩 더해가는 것이 된다.
3 5 7 이렇게 하나의 숫자들이 되는 것이다
8 15
23 이렇게 된다. 하지만 우리가 찾아야 하는 것은
마지막이 16이 되는 경우이다.
첫 줄을 1 2 3 4 배열을 다양하게 해서 찾으면 될 것 같다.
즉
1 / 2 / 3 / 4
1+2 / 2+3 / 3+4
1+2+2+3 / 2+3+3+4
1+2+2+2+3+3+3+4
결국 다 해보는 방법밖에 없다고 한다.
순열을 다해보는..4!의 가짓수가 나온다.>>24내가지의 시뮬레이션을 해보는 것이다.
1 2 3 4
1 2 4 3
1 3 2 4
...
그리고
16이 발견되었을 때 stop 하면 되겠지. 근데 만약 10개가 첫 줄의 경우 10!은 너무 크다...
수학적으로 할 수 있는 방법이 있다..!! 더하기 한 것의 규칙을 봐 보아라..

힌트 보았다.

만약 sum이 20이라면

양 끝의 수는 1번씩 더하고
그 안쪽 수는 3번씩 더해진다는 사실을 발견

1 2 1
1 3 3 1
1 4 6 4 1 의 규칙을 발견..
이것은 이항계수이자
조합 계산....

그 규칙을 구하면 아마 list를 통해 곱하기와 더하여 답을 수할 수 있지 않을까?! 니가 해봐라

선생님 코드

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


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)

다시 풀어 보아라..꼭..