[SWEA 5260][Python][파이썬 S/W 문제해결 최적화] 3일차 - 부분 집합의 합

코드

## SWEA 5260
T = int(input())
for test_case in range(1,T+1):
    N,K = map(int, input().split())
    result = 0
    arry = [ [N,0] ]
    while arry :
        cur = arry.pop()
        if cur[0] == 0 :
            continue
        
        bound = cur[0]*(cur[0]+1)/2 + cur[1]
        if bound >= K :
            if cur[0]+cur[1] == K :
                result += 1
            elif cur[0] + cur[1] < K :
                arry.append([ cur[0]-1,cur[0]+cur[1] ])

            arry.append([ cur[0]-1, cur[1] ])

    print(f"#{test_case} {result}")

 

풀이

낯선 문제였다.. 

백트랙킹을 진행하며 가지치기를 위한  Bound 조건을 찾아 해당 조건을 충족하지 못하면 반복하지 않도록 했다.

1부터 N까지 모든 양의 정수를 더하면 N*(N+1)/2 가 되므로 초기 bound 값으로 설정 후, 

bound가 K보다 큰 경우에만  N-1 ~ 1 값을 stack으로 넘겨주며 bound에 값을 업데이트 했다.