[SWEA 1486번] 장훈이의 높은 선반 - 파이썬(python)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV2b7Yf6ABcBBASw

SW Expert Academy

문제

장훈이는 서점을 운영하고 있다.

서점에는 높이가 B인 선반이 하나 있는데 장훈이는 키가 매우 크기 때문에, 선반 위의 물건을 자유롭게 사용할 수 있다.

어느 날 장훈이는 자리를 비웠고, 이 서점에 있는 N명의 점원들이 장훈이가 선반 위에 올려놓은 물건을 사용해야 하는 일이 생겼다.

각 점원의 키는 Hi로 나타나는데, 점원들은 탑을 쌓아서 선반 위의 물건을 사용하기로 하였다.

점원들이 쌓는 탑은 점원 1명 이상으로 이루어져 있다.

탑의 높이는 점원이 1명일 경우 그 점원의 키와 같고, 2명 이상일 경우 탑을 만든 모든 점원의 키의 합과 같다.

탑의 높이가 B 이상인 경우 선반 위의 물건을 사용할 수 있는데 탑의 높이가 높을수록 더 위험하므로 높이가 B 이상인 탑 중에서 높이가 가장 낮은 탑을 알아내려고 한다.

입력

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 두 정수 N, B(1 ≤ N ≤ 20, 1 ≤ B ≤ S)가 공백으로 구분되어 주어진다.

S는 두 번째 줄에서 주어지는 점원들 키의 합이다.

두 번째 줄에는 N개의 정수가 공백으로 구분되어 주어지며, 각 정수는 각 점원의 키 Hi (1 ≤ Hi ≤ 10,000)을 나타낸다.

출력

각 테스트 케이스마다 첫 번째 줄에는 ‘#t’(t는 테스트 케이스 번호를 의미하며 1부터 시작한다)를 출력하고, 만들 수 있는 높이가 B 이상인 탑 중에서 탑의 높이와 B의 차이가 가장 작은 것을 출력한다.

예제 풀이

테스트 케이스의 경우 키가 3, 3, 5, 6인 점원이 탑을 만들면 높이가 17(3 + 3 + 5 + 6)이 된다.

높이가 16인 탑은 만들 수 없으므로 높이가 17인 탑이 문제에서 구하려는 탑의 높이이다. 따라서 17 – 16 = 1이 답이 된다.

풀이

• 시간초과를 신경써야 하는 문제이다.
• 일반적인 DFS로 풀이할 경우 시간초과나기 쉽다.
• 합을 구하는 문제이므로 선택된 숫자의 순서는 중요하지 않으므로 조합의 방법으로 풀이한다.
• 대상이 되는 수를 더하거나 아니거나의 두가지로 나누어 함수를 호출해서 풀이했다.

코드

def dfs(level, summ):
    global mn
    if summ>mn:
        return
    if level==N:
        if summ >= B:
            if summ<mn:
                mn=summ
        return
    dfs(level+1,summ+H[level])
    dfs(level+1,summ)

T = int(input())
for test_case in range(1, T + 1):
    # N: 점원 수 , B: 선반 높이
    N,B =map(int, input().split())
    # H: 점원들의 키
    H = list(map(int, input().split()))
    visited = [0]*N
    mn=21e8
    dfs(0,0)
    print(f'#{test_case} {mn-B}')