[문제]
철수는 그의 바둑이들을 데리고 시장에 가려고 한다. 그런데 그의 트럭은 C킬로그램 넘게 태울수가 없다.
철수는 C를 넘지 않으면서 그의 바둑이들을 가장 무겁게 태우고 싶다.
N마리의 바둑이와 각 바둑이의 무게 W가 주어지면, 철수가 트럭에 태울 수 있는 가장 무거운 무게를 구하는 프로그램을 작성하세요.
▣ 입력설명
첫 번째 줄에 자연수 C(1<=C<=100,000,000)와 N(1<=N<=30)이 주어집니다.
둘째 줄부터 N마리 바둑이의 무게가 주어진다.
▣ 출력설명
첫 번째 줄에 가장 무거운 무게를 출력한다.
▣ 입력예제 1
259 5
81
58
42
33
61
▣ 출력예제 1
242
[풀이]
def dfs(l, sum, tsum): # l: 인덱스, sum: 부분집합의 합, tsum: 판단한 부분집합의 합
global result
# total-tsum: 앞으로 판단해야 할 바둑이들의 총 무게
if sum+(total-tsum) < result: # cut-edge 2번 조건
return # 밑으로 가지 뻗을 필요가 없음
if sum > c: # cut-edge 1번 조건
return
if l == n: # 종착점. 부분집합 1개 완성
if sum > result:
result = sum
else:
dfs(l+1, sum+a[l], tsum+a[l])
dfs(l+1, sum, tsum+a[l])
c, n = map(int, input().split())
a = [0] * n # 바둑이 각각의 무게
result = -2147000000 # 가장 큰 값을 구해야 하니, 아주 작은 값으로 초기화
for i in range(n):
a[i] = int(input())
total = sum(a)
dfs(0, 0, 0)
print(result)
[내용]
- 처음에 로직 자체를 이해하지 못했었다. 처음 잘못 이해한 로직:
1. 입력 받은 값들을 내림차순 sort =>
2. 아래 처럼 더한 값들과 c를 비교.
1+2
1+2+3
1+2+3+4
3. 더한 값 < c => 그 다음 값을 더해봄
4. 더한 값 == c => 이 값 출력
5. 더한 값 > c -> 이 전 값 까지만 더하고 출력
==========> 이전 문제 처럼 인덱스를 가지고 풀어야 한다.
- 2개 갈래인 상태트리를 만들어 DFS로 풀어야 한다. 여기서 DFS 함수 인자로는 상태트리의 레벨을 가리키는 인덱스(몇 마리를 태울 것인지를 의미)와 실시간으로 누적되는 바둑이들의 무게 합.
- 시간 복잡도 줄이기: Cut-edge 조건 추가!! ->
① 중간에 누적된 무게 합이 최대 몸무게(C) 보다 커지게 되는 순간 return
② 실시간으로 포함여부에 따라 갱신된 누적 무게 합을 총 제한 무게에서 뺀 값과 현재 탐색하고 있는 갈래 아래의 부분집합들을 모두 합한다고 해도 현재 갱신된 무게 합 보다 작다면 굳이 더 탐색할 필요 없음
'Coding Test > Python' 카테고리의 다른 글
| [python] 추억 점수 (0) | 2023.05.06 |
|---|---|
| [Python] 달리기 경주 (0) | 2023.05.05 |
| [python] 합이 같은 부분집합(DFS : 아마존 인터뷰) (0) | 2023.03.22 |
| [python] 부분집합 구하기(DFS) (0) | 2023.03.19 |
| [python] 재귀함수를 이용한 이진수 출력 (0) | 2023.03.15 |