56.양팔저울(DFS)
무게가 서로 다른 K개의 추와 빈 그릇이 있다. 모든 추의 무게는 정수이고, 그릇의 무게는 0
으로 간주한다. 양팔저울을 한 번만 이용하여 원하는 물의 무게를 그릇에 담고자 한다.
주어진 모든 추 무게의 합을 S라 하자. 예를 들어, 추가 3개이고, 각 추의 무게가 {1, 2, 6}이
면, S=9이고, 양팔저울을 한 번만 이용하여 1부터 S사이에 대응되는 모든 무게의 물을 다음과
같이 그릇에 담을 수 있다. X는 그릇에 담는 물의 무게이고, ⎕ 은 그릇을 나타낸다.
X 1 2 3 4 5 6 7 8 9
⎕ :1 ⎕ :2 ⎕ :(1+2) (⎕ +2):6 (⎕ +1):6 ⎕ :6 ⎕ :(1+6) ⎕ :(2+6) ⎕ :(1+2+6)
만약 추의 무게가 {1, 5, 7}이면 S=13이고, 그릇에 담을 수 있는 물의 무게는 {1, 2, 3, 4, 5, 6, 7, 8, 11, 12, 13}이고, 1부터 S사이에서 무게에서 9와 10에 대응하는 무게의 물을 담을수 없다.
K(3<=K<=13)개의 추 무게가 주어지면, 1부터 S사이의 정수 중 측정이 불가능한 물의 무게는
몇 가지가 있는 지 출력하는 프로그램을 작성하세요.
▣ 입력설명
첫 번째 줄에 자연수 K(3<=K<=13)이 주어집니다.
두 번째 줄에 K개의 각 추의 무게가 공백을 사이에 두고 주어집니다. 각 추의 무게는 1부터
200,000까지이다.
▣ 출력설명
첫 번째 측정이 불가능한 가지수를 출력하세요.
▣ 입력예제 1
3
1 5 7
▣ 출력예제 1
2
내 코드
def dfs(v,sum,tsum):
if sum+(s-tsum)<=0:
return
if v==k:
if sum not in res:
res.append(sum)
else:
dfs(v+1,sum+lst[v],tsum+lst[v])
dfs(v+1,sum,tsum+lst[v])
dfs(v+1,sum-lst[v],tsum+lst[v])
k=int(input())
lst=list(map(int, input().split()))
s=sum(lst)
res=[]
sum=0
dfs(0,0,0)
print(s-len(res))모든 경우의 수를 구했는데, 추를 더하는 경우, 빼는 경우, 아무것도 하지 않는 경우로 나누어서 재귀함수를 실행했다. 그리고 시간제한을 맞추기 위해 각 단계에서의 합인 tsum을 구해서 sum이 그 이후의 모든 합과 더해도 0보다 작거나 같으면 리턴하도록 했다.
하지만 여전히 시간초과가 나왔다.
풀이
def DFS(L, sum):
global res
if L==n:
if 0<sum<=s:
res.add(sum)
else:
DFS(L+1, sum+G[L])
DFS(L+1, sum-G[L])
DFS(L+1, sum)
if __name__=="__main__":
n=int(input())
G=list(map(int, input().split()))
s=sum(G)
res=set()
DFS(0, 0)
print(s-len(res))반성점
- 가지치기를 통해 시간을 줄여야 하는데 아는 방법이 얼마 없음
- set타입에 대해서 알고는 있었으나 생각하지 못함
배운 것
- 중복된 숫자가 많이 들어올 것으로 예상되면 (set을 사용 가능하다는 가정 하에) set을 사용하면 시간을 줄일 수 있다.
