장훈이의 높은 선반(SW Expert Academy, SWEA)

난이도 : D4

문제번호 : 1486

※ 저의 풀이가 무조건적인 정답은 아닙니다.

다른 코드가 좀더 효율적이고 좋을 수 있습니다.

다른사람들의 풀이는 언제나 참고만 하시기 바랍니다.

문제 주소 및 출처입니다.

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV2b7Yf6ABcBBASw&categoryId=AV2b7Yf6ABcBBASw&categoryType=CODE

SW Expert Academy

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

---

1. 문제 설명

장훈이는 서점을 운영하고 있다. 서점에는 높이가 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의 차이가 가장 작은 것을 출력한다.

예시

입력	출력
1 5 16 1 3 3 5 6	#1 1

---

2. 문제풀이

모든 경우의 수를 구해보면 된다. 이럴때 적절한 방식으로 DFS가 있다. 여기에 최소높이를 정했을때 이것을 넘어간다면 더이상 계산하지 않도록 설정하면 백트래킹이 가능해진다.

---

3. 소스코드

#D4 1486 장훈이의 높은선반
 
def dfs(idx, _sum):
    global min_num
    #합계가 이미 최소치를 넘어가면 계산안함
    if _sum >= min_num:
        return
    #마지막 까지 왔다면
    if idx >= N:
        #선반이상이고 최솟값보다 작을때 값갱신
        if _sum >= B:
            min_num = _sum
        return
    visited[idx] = True
    dfs(idx+1, _sum + height[idx])
    visited[idx] = False
    dfs(idx+1, _sum)
 
 
T = int(input())
for t in range(1, T+1):
    #N = 점원수, B = 선반높이
    N, B = map(int, input().split())
    height = list(map(int, input().split()))
    min_num = 987654321
    visited = [False] * N
    dfs(0, 0)
    print('#{} {}'.format(t, min_num - B))