- 일단 물 그릇과 추가 양팔 저울 상에서 균형을 유지해야 한다는 것을 생각해야 한다
- 그리고 물 그릇을 오른쪽에 고정한다고 가정하고 추는 왼쪽, 오른쪽, 혹은 아예 놓지 않는 3가지의 경우를 생각하여 물그릇에 물을 얼만큼 채워야 균형을 유지할지 고려하면 된다.
- 여기서 이제 주의해야 할 것은 물의 무게가 마이너스가 되는 경우는 문제에서 고려하지 않고 - 따라서 물의 무게가 플러스일 때만 고려했다
- 결과가 되는 물의 무게가 중복 될 수 있다는 것을 고려해야 한다 - 따라서 자료형 Set을 사용했다
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
def DFS(level, sum):
if level == n:
if sum > 0:
res.add(sum) # 물의 무게가 마이너스인 경우는 제외
else:
DFS(level+1, sum+weights[level]) # 추를 왼쪽에 놓는 경우
DFS(level+1, sum-weights[level]) # 추를 오른쪽에 놓는 경우
DFS(level+1, sum) # 추를 놓지 않는 경우
if __name__ == '__main__':
n = int(input())
weights = list(map(int, input().split()))
water = sum(weights)
res = set()
DFS(0, 0)
print(water - len(res)) # 물의 무게의 개수에서 위에서 계산되서 나온 물의 무게의 개수의 차를 print 해줬다
|
cs |
|
|
728x90
'Data Structures & Algorithms' 카테고리의 다른 글
| [Algorithms] 깊이/넓이 우선 탐색 (DFS, BFS) 활용-알파코드(DFS) (0) | 2022.05.28 |
|---|---|
| [Algorithms] 깊이/넓이 우선 탐색 (DFS, BFS) 활용-동전 바꿔주기(DFS) (0) | 2022.05.28 |
| [Algorithms] 완전탐색(백트랙킹, 상태트리와 CUT EDGE)/깊이우선탐색(DFS) Basic-경로 탐색(그래프 DFS) (0) | 2022.05.27 |
| [Algorithms] 완전탐색(백트랙킹, 상태트리와 CUT EDGE)/깊이우선탐색(DFS) Basic-인접 행렬(가중치 방향 그래프) (0) | 2022.05.27 |
| [Algorithms] 완전탐색(백트랙킹, 상태트리와 CUT EDGE)/깊이우선탐색(DFS) Basic-수들의 조합(DFS) (0) | 2022.05.26 |