coding test - python/기본기 문제
문제 / 바둑이 승차(DFS, 부분집합) / Python 파이썬
sillon
2022. 10. 2. 22:14
728x90
반응형
문제 제목: 바둑이 승차(DFS)
철수는 그의 바둑이들을 데리고 시장에 가려고 한다. 그런데 그의 트럭은 C킬로그램 넘게 태 울수가 없다. 철수는 C를 넘지 않으면서 그의 바둑이들을 가장 무겁게 태우고 싶다. N마리의 바둑이와 각 바둑이의 무게 W가 주어지면, 철수가 트럭에 태울 수 있는 가장 무거운 무게를 구하는 프로그램을 작성하세요.
기본기 문제에 있는 부분집합 구하기 문제를 참고하였다.
먼저 입력받는 값을 구현함
arr = [0]
m, n = map(int,input().split())
for _ in range(n):
arr.append(int(input()))
그리고 각각 구한 부분집합들을 저장하기위해 dfs_list 를 선언해주었다. (전역변수로 해서 DFS를 통해 구한 부분집합을 dfs_list안에 넣어 줄 것임)
그리고 나머지 부분은 부분집합의 문제와 동일
if __name__ == "__main__":
dfs_list = []
arr = [0]
m, n = map(int,input().split())
for _ in range(n):
arr.append(int(input()))
ch = [0]*(n+1)
DFS(1)
print(dfs_list)dfs 함수 구현 부분
def DFS(v):
global dfs_list
global arr
if v == n+1:
tmp = [] #부분집합
for i in range(1, n+1):
if ch[i] == 1:
tmp.append(arr[i]) # ch=1이면 해당 값을 포함
print(tmp)
dfs_list.append(tmp)
else:
ch[v] = 1 # 해당 값을 부분집합에 포함한다
DFS(v+1)
ch[v] = 0 # 해당 값을 포함하지 않음
DFS(v+1)
print()
return dfs_list
여기까지 구현하여 출력하면 다음과같이 부분집합이 구해짐을 알 수 있다.
def DFS(v):
global dfs_list
global arr
if v == n+1:
tmp = []
for i in range(1, n+1):
if ch[i] == 1:
tmp.append(arr[i])
print(tmp)
dfs_list.append(tmp)
else:
ch[v] = 1
DFS(v+1)
ch[v] = 0
DFS(v+1)
print()
return dfs_list
if __name__ == "__main__":
dfs_list = []
arr = [0]
m, n = map(int,input().split())
for _ in range(n):
arr.append(int(input()))
ch = [0]*(n+1)
DFS(1)
print(dfs_list)
해당 부분집합에서 철수는 C를 넘지 않으면서 그의 바둑이들을 가장 무겁게 태우고 싶다 는 조건만 완성하면 된다.
따라서 부분집합에서 C값을 넘는 것 dfs list 에 포함하지 않는다.
(코드 상에서 C값은 m으로 표현했다.)
if sum(tmp) < m:
dfs_list.append(tmp)
마지막에 부분집합의 합을 계산하여 최대를 출력하는 코드 작성
sum_list = []
for i in dfs_list:
sum_list.append(sum(i))
print(max(sum_list))
나의 풀이
import sys
def DFS(v):
global dfs_list
global arr
if v == n+1:
tmp = []
for i in range(1, n+1):
if ch[i] == 1:
tmp.append(arr[i])
if sum(tmp) < m:
dfs_list.append(tmp)
else:
ch[v] = 1
DFS(v+1)
ch[v] = 0
DFS(v+1)
return dfs_list
if __name__ == "__main__":
dfs_list = []
arr = [0]
m, n = map(int,input().split())
for _ in range(n):
arr.append(int(input()))
ch = [0]*(n+1)
DFS(1)
sum_list = []
for i in dfs_list:
sum_list.append(sum(i))
print(max(sum_list))
모범답안
import sys
from collections import deque
def DFS(L, sum):
global result
# L : 인덱스 번호
# sum: 부분집합 합
if L == n: # 종착점에 온 것. 부분 집합 하나가 만들어진 종학점
if sum > result:
result = sum
else:
DFS(L+1, sum+a[L]) # a[l]번째를 부분집합으로 참여
DFS(L+1, sum) # a[l]번째를 부분집합으로 참여시키지 않음
if __name__ == "__main__":
c,n = map(int,input().split())
a = [0] * n
result = -2147000000 # 답을 저장 (초기화는 가장 작은 값으로)
arr = [0]
for i in range(n):
a[i] = int(input())
DFS(0,0)
print(result)
import sys
from collections import deque
def DFS(L, sum):
global result
# L : 인덱스 번호
# sum: 부분집합 합
if sum > c:
return # 무게제한
if L == n: # 종착점에 온 것. 부분 집합 하나가 만들어진 종학점
if sum > result:
result = sum
else:
print("index: ", L,", Sum: ", sum,", a[L]: ", a[L], ", sum + a[L]: ", sum + a[L])
DFS(L+1, sum+a[L]) # a[l]번째를 부분집합으로 참여 (바둑이 더 태운다)
DFS(L+1, sum) # a[l]번째를 부분집합으로 참여시키지 않음 (바둑이 태우지마!)
if __name__ == "__main__":
c,n = map(int,input().split())
a = [0] * n
result = -2147000000 # 답을 저장 (초기화는 가장 작은 값으로)
arr = [0]
for i in range(n):
a[i] = int(input())
DFS(0,0)
print(result)
'''
259 5
81
58
42
33
61
'''출력 결과
index: 0 , Sum: 0 , a[L]: 81 , sum + a[L]: 81
index: 1 , Sum: 81 , a[L]: 58 , sum + a[L]: 139
index: 2 , Sum: 139 , a[L]: 42 , sum + a[L]: 181
index: 3 , Sum: 181 , a[L]: 33 , sum + a[L]: 214
index: 4 , Sum: 214 , a[L]: 61 , sum + a[L]: 275
index: 4 , Sum: 181 , a[L]: 61 , sum + a[L]: 242
index: 3 , Sum: 139 , a[L]: 33 , sum + a[L]: 172
index: 4 , Sum: 172 , a[L]: 61 , sum + a[L]: 233
index: 4 , Sum: 139 , a[L]: 61 , sum + a[L]: 200
index: 2 , Sum: 81 , a[L]: 42 , sum + a[L]: 123
index: 3 , Sum: 123 , a[L]: 33 , sum + a[L]: 156
index: 4 , Sum: 156 , a[L]: 61 , sum + a[L]: 217
index: 4 , Sum: 123 , a[L]: 61 , sum + a[L]: 184
index: 3 , Sum: 81 , a[L]: 33 , sum + a[L]: 114
index: 4 , Sum: 114 , a[L]: 61 , sum + a[L]: 175
index: 4 , Sum: 81 , a[L]: 61 , sum + a[L]: 142
index: 1 , Sum: 0 , a[L]: 58 , sum + a[L]: 58
index: 2 , Sum: 58 , a[L]: 42 , sum + a[L]: 100
index: 3 , Sum: 100 , a[L]: 33 , sum + a[L]: 133
index: 4 , Sum: 133 , a[L]: 61 , sum + a[L]: 194
index: 4 , Sum: 100 , a[L]: 61 , sum + a[L]: 161
index: 3 , Sum: 58 , a[L]: 33 , sum + a[L]: 91
index: 4 , Sum: 91 , a[L]: 61 , sum + a[L]: 152
index: 4 , Sum: 58 , a[L]: 61 , sum + a[L]: 119
index: 2 , Sum: 0 , a[L]: 42 , sum + a[L]: 42
index: 3 , Sum: 42 , a[L]: 33 , sum + a[L]: 75
index: 4 , Sum: 75 , a[L]: 61 , sum + a[L]: 136
index: 4 , Sum: 42 , a[L]: 61 , sum + a[L]: 103
index: 3 , Sum: 0 , a[L]: 33 , sum + a[L]: 33
index: 4 , Sum: 33 , a[L]: 61 , sum + a[L]: 94
index: 4 , Sum: 0 , a[L]: 61 , sum + a[L]: 61
242
Process finished with exit code 0
이것두 시간 초과한다..
그렇다면 방법은 조금 더 Cut Edge 한다는 것!
남은 바둑이들을 다 더하더라도 해당 더한 값이 result보다 작아지면 cut 한다.
그렇게 컷하면 됨
sum : 현재까지 더한 값
total: 바둑이 전체를 더한 값
tsum: 이미 태운 바둑이들의 합
total - tsum: 앞으로 태울 바둑이들
sum + (total - tsum): 현재 바둑이들 합 + 앞으로 태울 남은 바둑이들 합
현재 바둑이들 합 + 앞으로 태울 남은 바둑이들 합이 result ( 부분집합의 최댓값 ) 보다 적다면
함수 종료
(가지치기 푸루닝~)
def DFS(L, sum,tsum):
global result
# L : 인덱스 번호
# sum: 부분집합 합
if sum + (total - tsum) < result :# 앞으로 판단해야할 바둑이들의 합이 result 보다 적더라 -> 가지 뻗을 필요가 없음
return
if sum > c:
return # 무게제한
if L == n: # 종착점에 온 것. 부분 집합 하나가 만들어진 종학점
if sum > result:
result = sum
else:
print("index: ", L,", Sum: ", sum,", a[L]: ", a[L], ", sum + a[L]: ", sum + a[L])
DFS(L+1, sum+a[L],tsum + a[L]) # a[l]번째를 부분집합으로 참여
DFS(L+1, sum,tsum + a[L]) # a[l]번째를 부분집합으로 참여시키지 않음
if __name__ == "__main__":
c,n = map(int,input().split())
a = [0] * n
result = -2147000000 # 답을 저장 (초기화는 가장 작은 값으로)
arr = [0]
for i in range(n):
a[i] = int(input())
total = sum(a)
DFS(0,0,0)
print(result)
출력 결과
index: 0 , Sum: 0 , a[L]: 81 , sum + a[L]: 81
index: 1 , Sum: 81 , a[L]: 58 , sum + a[L]: 139
index: 2 , Sum: 139 , a[L]: 42 , sum + a[L]: 181
index: 3 , Sum: 181 , a[L]: 33 , sum + a[L]: 214
index: 4 , Sum: 214 , a[L]: 61 , sum + a[L]: 275
index: 4 , Sum: 181 , a[L]: 61 , sum + a[L]: 242
242
ㅊ
※ 알아야 할 것
- 적절한 DFS 의 가지치기가 필요하당
728x90
반응형