📍문제
농부 존은 최근 소들이 사용할 수 있는 도서관을 조성하기 위해 책장을 하나 더 구입했습니다.
하지만 구입한 지 얼마되지 않았는데도 책장은 굉장히 빠른 속도로 가득 차고 있으며, 이제 사용 가능한 공간은 맨 위쪽 선반 뿐입니다!
농부 존은 N마리의 소 (1 <= N <= 20)을 가지고 있습니다.
그리고 이 각각의 소는 높이 (1 <= <= 1,000,000 : 이소들은 매우 키가 큽니다!)를 가지고 있습니다.
책장의 높이는 B입니다.
(1 <= <= S, 여기서 S는 모든 소의 높이의 합입니다).
책장의 맨 위에 도달하기 위해 하나 이상의 소가 위로 올라갈 수 있으며, 이 소들의 총 높이는 각각 소들의 키의 합이어야 합니다.
이 총 소 높이는 책장의 높이보다 작아서는 안됩니다.
그 중에서도 책장과 가장 차이가 적은, 그 최적의 높이를 찾아내기 위해 여러분은 따로 그 작업을 수행해야 합니다.
이 차이(소들의 키 - 책장 높이)는 소 stack의 높이와 책장 사이의 높이 차이를 의미합니다.
그리고 이 차이들 중에서도 가능한 한 작아야 합니다.
프로그램은 최적의 소 스택을 찾아 책장에 도달할 수 있는 최소한의 차이를 출력해야 합니다.
입력
1행: 두 개의 공백으로 구분된 정수: N과 B
2행 ~ N+1행까지: 각 행은 하나의 정수를 받을 수 있어야 하며, 각 i번째 행은 를 나타냅니다
출력
1행: 소 스택과 책장 사이의 높이 차가 최소가 되는, 그 소 스택의 총 높이와 그 차이를 나타내는 하나의 정수
📍아이디어
사실 그리디로 풀어도 되는 문제이지만, DFS 포함 그래프 탐색 문제를 너무 안 다뤄서 모든 알고리즘을 까먹은 나머지...
DFS 알고리즘으로 풀었다.
각 소들의 높이를 배열에 저장한 다음, 현재까지 선택한 소들의 높이를 저장할 수 있는 변수를 따로 만들어서 저장하였다.
그 후 책장과 소들 높이의 차를 저장할 차이를 저장할 변수를 따로 만들어 가장 큰 값(sys.maxmize())을 할당하였다.
그 후 소의 높이가 담긴 배열, 현재 탐색 중인 소의 인덱스, 현재까지 선택한 소의 높이 합을 파라미터로 하는 dfs 함수를 만들었다.
현재까지 선택한 소의 높이 합이 m 이상이면 현재까지의 높이가 책장 높이를 넘었으므로, 최소 높이 차이를 업데이트하고 현재까지의 높이를 정답이 담긴 ans 배열에 추가하였다.
그런 다음, 현재 소를 선택하는 경우와 선택하지 않는 경우, 두 가지 경우를 고려하여 DFS를 재귀적으로 호출하여 탐색을 진행하였다.
이런식으로 탐색을 반복하다 보면,
최종적으로 ans 배열에는 선택된 소들의 높이가, 최소 차이를 저장하는 변수에는 최소 높이 차이가 저장된다.
코드의 마지막 부분에서는 ans 배열이 비어있는 경우, 모든 소의 높이를 합쳐도 책장 높이를 넘지 못하는 경우를 의미하므로 이를 고려해서 출력한다.
📍제출코드
n, m = map(int, input().split())
cow = []
ans = []
for _ in range(n):
cow.append(int(input()))
hap = 0
cha = float('inf')
def dfs(cow, i, current_height):
global hap
global cha
if current_height >= m:
cha = min(cha, current_height - m)
ans.append(current_height)
return
if i >= n:
return
# 현재 소를 선택한 경우
dfs(cow, i + 1, current_height + cow[i])
# 현재 소를 선택하지 않은 경우
dfs(cow, i + 1, current_height)
dfs(cow, 0, 0)
if ans:
print(cha)
else:
print(m) # 모든 소의 높이를 합쳐도 책장 높이를 넘지 못하는 경우
