[Algorithm] SWEA : 1486. 장훈이의 높은 선반 by Python

📌 문제 설명

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

---

💡 문제 풀이

재귀 + 백트래킹을 활용하는 대표적인 문제 중 하나다.

 

step 1)
변수 선언

• numbers : 점원들의 키를 담은 배열
• res : 문제의 정답을 담는 변수 - 최소값을 찾으므로 큰 값으로 초기화!
• solve : 문제 해결을 위해 작성한 (재귀)함수

step 2)
재귀 함수를 통하여 점원들이 탑을 쌓을 수 있는 모든 경우('조합')를 확인해야 한다.

따라서 함수의 인자에 0(인덱스), 0(키의 총합)값을 넣어 탐색을 시작한다.
→ 재귀의 종료는 배열을 다 탐색했을 때(n == N)이다.

 

종료시점에 이르기 까지 배열의 원소를 더하거나 넘어가는 방식으로 모든 경우의 수에 대해 탐색한다.

 

step 3)
재귀의 종료시점이 되면 키의 총합(total)이 B보다 같거나 큰지 확인한다.
동시에, res에는 키의 총합과 선반의 높이(B)차가 최소인 값을 넣어야 한다.
위의 두 조건을 만족하면 res에 total-B 값을 최신화한다.

 

추가적으로 재귀를 진행하면서 가지치기를 하였다. 최소값을 찾는 것이 목표이기 때문에 진행중에 total-B 값이 res보다 같거나 크면 return하도록 코드를 작성하였다.

 

코드는 다음과 같다.

 

def solve(n, total):
    global N, B, res
    if n == N:
        if total >= B and res > total - B:
            res = total - B
        return
    if total - B >= res: return
    solve(n+1, numbers[n] + total)
    solve(n+1, total)

T = int(input())
for tc in range(T):
    N, B = map(int, input().split())
    numbers = list(map(int, input().split()))
    res = 0xffffff
    solve(0, 0)
    print('#{} {}'.format(tc+1, res))