https://www.acmicpc.net/problem/2437

 

2437번: 저울

하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓

www.acmicpc.net

문제 해결을 위한 과정

이 문제의 경우 골드 3 티어 문제로 저는 굉장히 어렵게 풀었던 문제입니다. 그리디 알고리즘으로 해결할 수 있는 문제인데 우선 알아야 하는 것이 있습니다. 바로 1부터 X - 1까지 만들 수 있는 금액이라고 가정을 했을 때 X가 새로 들어온 화폐단위인 a[i]보다 크다면 X원은 만들 수 없다는 것입니다. 이 경우는 저는 암기를 하기로 결정하였습니다. 크루스칼 알고리즘도 그리디이긴 하지만 암기가 필요한 부분입니다. 따라서 해당하는 경우도 암기를 바탕으로 해결합시다.

문제 해결을 위한 팁

팁까지는 아니지만 꼭 짚고 넘어가야할 조건이 있습니다. 바로 리스트가 정렬이 된 상태이어야만 한다는 것입니다.

소스코드

 

1
2
3
4
5
6
7
8
9
10
11
n = int(input())
data = list(map(int, input().split()))
data.sort()
 
target = 1
for x in data:
  if target < x:
    break
  target += x
 
print(target)
 cs

 

'알고리즘 > 백준' 카테고리의 다른 글

백준 알고리즘 13305: 주유소(Python)  (0) 2021.01.19
백준 알고리즘 1715: 카드 정렬하기 (Python)  (0) 2021.01.11
백준 알고리즘 18353: 병사 배치하기(Python)  (0) 2020.12.21
백준 알고리즘 14501: 퇴사 (Python)  (1) 2020.12.19
백준 알고리즘 1932: 정수 삼각(Python)  (0) 2020.12.18
개념

크루스컬 알고리즘은 대표적인 최소 신장 트리 알고리즘입니다. 최소 신장 트리란 그래프가 주어져 있을 때 모든 노드들을 포함하고 있으며 사이클이 존재하지 않는 무방향 그래프를 의미합니다. 즉 모든 노드가 연결이 되어있어야 한다는 점과 사이클이 존재하지 않는다는 조건의 교집합이라고 할 수 있습니다. 다음 그림을 보겠습니다. (그림은 나동빈 님의 이것이 취업을 위한 코딩 테스트이다. 를 참고하였습니다.) 

위 그림의 경우 모든 노드들은 연결이 되어있고 사이클이 존재하지 않으므로 신장 트리 입니다. 간선의 개수는 노드의 개수 -1 인 것을 확인할 수 있습니다. 크루스컬 알고리즘은 가능한 신장 트리 중 가장 최소의 비용으로 신장 트리를 연결하는 알고리즘입니다. 과정은 다음과 같습니다.

1. 모든 간선 정보를 따로 리스트에 저장한다. 

2. 리스트에 저장된 간선 정보를 cost가 작은순으로 정렬한 후 사이클의 존재 유무를 파악한다.

3. 사이클이 아닐경우 두 노드를 연결한다.

4. 사이클일 경우 넘어간다. 

소스코드

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
def find_parent(parent, x):
  if parent[x] != x:
    parent[x] = find_parent(parent, parent[x])
  return parent[x]
 
def union_parent(parent, a, b):
  a = find_parent(parent, a)
  b = find_parent(parent, b)
  if a < b:
    parent[b] = a
  else:
    parent[a] = b
 
v, e = map(int, input().split())
parent = [0] * (1 + v)
 
for i in range(1, 1  + v):
  parent[i] = i
 
result = 0
edges = []
 
for i in range(e):
  a, b, cost = map(int, input().split())
  edges.append((cost, a, b))
 
edges.sort()
 
for edge in edges:
  cost, a, b = edge
  if find_parent(parent, a) != find_parent(parent, b):
    union_parent(parent, a, b)
    result += cost
 
print(result)
 cs

 

'알고리즘 > 알고리즘 이론' 카테고리의 다른 글

벨만 포드 알고리즘  (0) 2021.03.01
사이클 판별 알고리즘 (Python  (0) 2020.12.31
서로소 집합 알고리즘 (Python)  (0) 2020.12.30
다익스트라 알고리즘 (Python)  (0) 2020.12.22
편집거리 알고리즘 (Python)  (0) 2020.12.22

+ Recent posts

티스토리툴바