<div id="readability-page-1" class="page"><div><h2 id="바둑이-승차">바둑이 승차</h2>
참고자료: <a href="https://www.inflearn.com/course/%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8/lecture/26956?tab=curriculum&amp;speed=2">파이썬 알고리즘 문제풀이</a>
상기 강의 내용을 바탕으로 swift 코드로 바꿔서 요약 정리한 내용입니다.
<ul>
<li>문제</li>
</ul>
철수의 트럭의 제한무게는 c이다. 철수는 n마리의 바둑이들을 키우고 있는데, 트럭에 최대한 무겁게 바둑이들을 태워서 시장에 갈 예정이다. n마리의 바둑들의 수와 그 무게가 주어지면, 트럭에 태울 수 있는 가장 무거운 무게를 출력하는 프로그램을 작성하시오.
<ul>
<li>입력예제</li>
</ul>
259 5 
81 
58 
42 
33 
61
<ul>
<li>출력예제</li>
</ul>
242
<h2 id="내-풀이">내 풀이</h2>
<pre><code>func dfs(_ idx:Int, _ sum:Int, _ nSum: Int) {
 if sum + (total-nSum) &lt; res { return }
 if sum &gt; c { return }
 if idx == n {
 res = sum &gt; res ? sum:res
 } else {
 dfs(idx+1, sum+list[idx], nSum+list[idx])
 dfs(idx+1, sum, nSum+list[idx])
 }
}

let input = readLine()!.split{$0==" "}.map{Int(String($0))!}
let (c, n) = (input[0], input[1])
var list = [Int](repeating: 0, count: n)
var res = -2147000
for idx in 0..&lt;n {
 list[idx] = Int(readLine()!)!
}
let total = list.reduce(0,+)
dfs(0, 0, 0)
print(res)</code></pre>
지난 부분집합 문제와 로직이 같다. 부분집합 중 가장 큰값을 구하는 로직을 구현한 뒤에, 정답이 될 수 없는 엣지케이스를 제외해준다(해당 부분은 시간복잡도에서 이점을 갖기 위함이며 정답과는 관련없다).
예를들면 지금까지의 바둑이의 무게를 모두 더해준 nSum의 값을 total에서 뺀 값(아직 탐색하지 않은 남은 경우의 수를 모두 더해준다고 가정한 값)에 sum을 더해준 값이 res보다 작다면 함수를 종료시킨다.
그리고 트럭의 제한무게를 넘으면 안되기때문에, sum이 c를 넘어가는 경우에도 곧바로 함수를 종료시키면 된다.
<h2 id="강의-풀이">강의 풀이</h2>
풀이로직에서 차이가 없기 때문에 파이썬코드만 살펴보겠다.
<h2 id="파이썬-코드">파이썬 코드</h2>
<pre><code>def DFS(L, sum, tsum):
 global result
 if sum+(total-tsum)&lt;result:
 return
 if sum&gt;c:
 return
 if L==n:
 if sum&gt;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)</code></pre></div></div>

PS & Algorithm

WooSeok Suh

바둑이 승차
참고자료: 파이썬 알고리즘 문제풀이
상기 강의 내용을 바탕으로 swift 코드로 바꿔서 요약 정리한 내용입니다.
문제
철수의 트럭의 제한무게는 c이다. 철수는 n마리의 바둑이들을 키우고 있는데, 트럭에 최대한 무겁게 바둑이들을 태워서 시장에 갈 예정이다. n마리의 바둑들의 수와 그 무게가 주어지면, 트럭에 태울 수 있는 가장 무거운 무게를 출력하는 프로그램을 작성하시오.
입력예제
259 5
81
58
42
33
61
출력예제
242
내 풀이
func dfs(_ idx:Int, _ sum:Int, _ nSum: Int) {
 if sum + (total-nSum) < res { return }
 if sum > c { return }
 if idx == n {
 res = sum > res ? sum:res
 } else {
 dfs(idx+1, sum+list[idx], nSum+list[idx])
 dfs(idx+1, sum, nSum+list[idx])
 }
}
let input = readLine()!.split{$0==" "}.map{Int(String($0))!}
let (c, n) = (input[0], input[1])
var list = [Int](repeating: 0, count: n)
var res = -2147000
for idx in 0..<n {
 list[idx] = Int(readLine()!)!
}
let total = list.reduce(0,+)
dfs(0, 0, 0)
print(res)
지난 부분집합 문제와 로직이 같다. 부분집합 중 가장 큰값을 구하는 로직을 구현한 뒤에, 정답이 될 수 없는 엣지케이스를 제외해준다(해당 부분은 시간복잡도에서 이점을 갖기 위함이며 정답과는 관련없다). 
예를들면 지금까지의 바둑이의 무게를 모두 더해준 nSum의 값을 total에서 뺀 값(아직 탐색하지 않은 남은 경우의 수를 모두 더해준다고 가정한 값)에 sum을 더해준 값이 res보다 작다면 함수를 종료시킨다.
그리고 트럭의 제한무게를 넘으면 안되기때문에, sum이 c를 넘어가는 경우에도 곧바로 함수를 종료시키면 된다.
강의 풀이
풀이로직에서 차이가 없기 때문에 파이썬코드만 살펴보겠다.
파이썬 코드
def DFS(L, sum, tsum):
 global result
 if sum+(total-tsum)<result:
 return
 if sum>c:
 return
 if L==n:
 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)

완전탐색 - DFS(4)

댓글