[SWEA] D4 1486. 장훈이의 높은 선반 / python

출처 : swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV2b7Yf6ABcBBASw&categoryId=AV2b7Yf6ABcBBASw&categoryType=CODE&problemTitle=%EC%9E%A5%ED%9B%88&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

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이 답이 된다.

 

입력1
5 16
1 3 3 5 6
 

출력#1 1

 

 

Think Think 💥

1. 입력1로 예를 들었을 때 ( 1 3 3 ), ( 1 5 6 ), ( 6 ), ( 3 5 6 ), ( 5 6 ) 등등의 case를 모두 고려해야 하기 때문에 부분집합으로 풀어야 한다. 

 

2. 부분집합을 나타내는 방법은 여러가지가 있는데 N개의 0으로 이루어진 visited 리스트를 만들고 0과 1을 활용하여 부분집합을 나타낼 수 있다. 1인 경우면 선택된 것, 0인 경우면 제외된 것.

(1 5 6 )을 예시로 들면 이 경우 0으로 이루어진 리스트는 [ 1 0 0 1 1 ] 이 상태일 것이다.

 

3. 예시를 들면 아래와 같다 ( 2^5이니 총 32가지 )

 

 

4. 우리가 궁금한건 각 부분집합의 키의 합이니 visited의 해당 인덱스의 값을 곱해주고 더해주면서 재귀 파라미터로 넘겨주면 된다. 부분집합에서 0인 경우면 곱해서 0이 될테니 선택안된거나 마찬가지이기 때문이다.

 

 

 

코드 구현 👀