문제 : 1486. 장훈이의 높은 선반
문제
장훈이는 서점을 운영하고 있다.
서점에는 높이가 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이 답이 된다.
예제 입력
10 <--- 테스트 케이스 개수
5 16 <--- N,B
3 1 3 5 6 <--- N개의 숫자들
2 10
7 7
3 120
83 64 36
4 416
299 239 116 128
5 1535
351 228 300 623 954
10 2780
268 61 201 535 464 168 491 275 578 153
10 1162
73 857 502 826 923 653 168 396 353 874
15 8855
3711 576 9081 3280 1413 6818 5142 2981 1266 484 5757 2451 6961 4862 2086
15 57209
8903 5737 3749 8960 724 6295 1240 4325 8023 3640 2223 639 4161 5330 4260
20 78988
3811 2307 3935 5052 4936 3473 6432 7032 1560 1992 5332 7000 4020 9344 2732 8815 9924 8998 9540 4640
예제 출력
#1 1
#2 4
#3 27
#4 11
#5 42
#6 32
#7 2
#8 3
#9 25
#10 0
문제 해석
입력값의 첫번째 값은 테스크 케이스의 개수(예제에서는 10개)이고, 다음 두 줄을 확인해보면 N과 B가 적혀 있고, 다음줄에는 N개의 숫자들이 적혀있다. 우리는 N개의 숫자들을 잘 조합해서 B보다 큰 숫자들 중 가장 작은 값을 출력해야 한다.
처음에는 입력값을 받을 초기 셋팅을 해보자.
|
1
2
3
4
5
6
7
|
T = int(input())
for Count in range(T):
print("#{0} ".format(Count+1),end = '') #### 출력값 형태가 #1, #2.. 이런식이니 앞에서 먼저 출력해주었다.
N , B = map(int,input().split()) #### N과 B를 입력 받는다.
List = list(map(int,input().split())) #### 다음 줄을 List라는 리스트로 입력받는다.
total = 0 #### 이제부터 List를 받는 값들을 total이라는 변수로 다 합할것이다.
Answer = [] #### 뒤에서 보겠지만 total이 B보다 크면 Answer에 append시킬것이다. 그것을 위한 리스트이다.
|
cs |
이제 List에서 어떻게 애들을 사용할지 생각해보자. List의 앞에서부터 사용하고, 반납하는 방식으로 하면 어떨까라는 생각이 들어서 append와 pop을 사용하는 방법을 써보았다. 그래서 아래와 같이 새로운 함수 bubun을 만들어 코딩하였다.
|
1
2
3
4
5
6
7
8
9
|
def bubun(idx):
global total
if total >= B:
Answer.append(total)
if idx < N:
total += List[idx]
bubun(idx+1)
total -= List[idx]
bubun(idx+1)
|
cs |
방식은 List[idx]를 한 번 사용하고 재귀로 돌아가고, 다 쓰고 나면 다시 안썻을 때로 재귀를 시킨 것이다. Answer에는 total값이 B보다 클 때 마다 append를 시켜주었다. 백준 문제 N과 M 시리즈와 비슷한 문제였다. 출력값은 지금까지 구한 total에서 가작 작은 값에서 선반 길이만큼 뺀 값을 출력해야 하므로 나중에 print(min(Answer) - B)를 해주도록 한다. 결과를 확인해 보도록 한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
T = int(input())
for Count in range(T):
print("#{0} ".format(Count+1),end = '')
N , B = map(int,input().split())
List = list(map(int,input().split()))
total = 0
Answer = []
def bubun(idx):
global total
if total >= B:
Answer.append(total)
if idx < N:
total += List[idx]
bubun(idx+1)
total -= List[idx]
bubun(idx+1)
bubun(0)
print(min(Answer) - B)
|
cs |
더 간략하게 짤 수 있는 방법 있으면 알려주세요!! 아직 초보자라 직관적으로 풀었습니다.
출처
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV2b7Yf6ABcBBASw&
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
'SWExpert > D4' 카테고리의 다른 글
| [D4] 1258. [S/W 문제해결 응용] 7일차 - 행렬찾기 (Python 파이썬 풀이) (0) | 2020.02.27 |
|---|