문제 바로가기
문제:
19학번 이준석은 학생이 N명인 학교에 입학을 했다. 준석이는 입학을 맞아 모든 학생과 친구가 되고 싶어한다. 하지만 준석이는 평생 컴퓨터랑만 대화를 하며 살아왔기 때문에 사람과 말을 하는 법을 모른다. 그런 준석이에게도 희망이 있다. 바로 친구비다! 학생 i에게 Ai만큼의 돈을 주면 그 학생은 1달간 친구가 되어준다! 준석이에게는 총 k원의 돈이 있고 그 돈을 이용해서 친구를 사귀기로 했다. 막상 친구를 사귀다 보면 돈이 부족해질 것 같다는 생각을 하게 되었다. 그래서 준석이는 “친구의 친구는 친구다”를 이용하기로 했다. 준석이는 이제 모든 친구에게 돈을 주지 않아도 된다! 위와 같은 논리를 사용했을 때, 가장 적은 비용으로 모든 사람과 친구가 되는 방법을 구하라.
입력:
첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. (1 ≤ Ai ≤ 10,000, 1 ≤ i ≤ N) 다음 M개의 줄에는 숫자 v, w가 주어진다. 이것은 학생 v와 학생 w가 서로 친구라는 뜻이다. 자기 자신과 친구일 수도 있고, 같은 친구 관계가 여러 번 주어질 수도 있다.
출력:
준석이가 모든 학생을 친구로 만들 수 있다면, 친구로 만드는데 드는 최소비용을 출력한다. 만약 친구를 다 사귈 수 없다면, “Oh no”(따옴표 제거)를 출력한다.
풀이:
처음에는 union-find 를 사용하여 그룹별로 묶어서 풀려고 했다.
import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')
n, m, k = map(int, sys.stdin.readline().split())
# 비용기준 정렬
A = sorted([(idx, cost) for idx,cost in enumerate(list(map(int,sys.stdin.readline().split())),start=1)], key = lambda x:x[1])
# 처음 부모는 자기 자신
parents = [i for i in range(n+1)]
def find(x):
# 자기자신이 부모가 아니면
if parents[x] != x:
parents[x] = find(parents[x])
return parents[x]
def union(a, b):
a = find(a)
b = find(b)
if a < b:
parents[b] = a
else:
parents[a] = b
# 누가 더 작은 지 찾아봄
for i in range(m):
v, w = map(int, sys.stdin.readline().split())
# 부모 찾기
x = find(v); y = find(w)
# 합쳐야함 원래는 작은수로 합치지만, 이 문제에선 작은 비용 기준으로 해야한다.
union(x,y)
total_cost = 0
for i in range(1, n + 1):
idx, cost = A[i - 1]
if find(idx) != find(0) and total_cost + cost <= k:
union(0, idx)
total_cost += cost
if total_cost == k:
print(total_cost)
exit()
print("Oh no")
하지만 4퍼센트에서 틀린다. 원래 union-find 는 부모 값을 비교하여 작은 값의 인덱스가 부모인데, 이 문제는 작은 친구비용을 기준으로 해야하는데 그것을 어떻게 처리해야하는지 잘 몰라서 일단 제출했다.
2번째 시도
각 그룹별로 속하는 숫자들을 defaultdict으로 정리해두고
그룹마다 포문을 돌아 가장 작은 값을 찾아 그 값을 totol 에 더하는 식
import sys
from collections import defaultdict
n, m, k = map(int, sys.stdin.readline().split())
# 비용기준 정렬
A = [(0,0)] + sorted([(idx, cost) for idx,cost in enumerate(list(map(int,sys.stdin.readline().split())),start=1)], key = lambda x:x[1])
# 처음 부모는 자기 자신
parents = [i for i in range(n+1)]
def find(x):
# 자기자신이 부모가 아니면
if parents[x] != x:
parents[x] = find(parents[x])
return parents[x]
def union(a, b):
a = find(a)
b = find(b)
if a < b:
parents[b] = a
else:
parents[a] = b
# 누가 더 작은 지 찾아봄
for i in range(m):
v, w = map(int, sys.stdin.readline().split())
# 부모 찾기
x = find(v); y = find(w)
# 합쳐야함 원래는 작은수로 합치지만, 이 문제에선 작은 비용 기준으로 해야한다.
union(x,y)
# 각 그룹별로 속한 숫자 나눔
result_dict = defaultdict(list)
for index, value in enumerate(parents):
result_dict[value].append(index)
group = set(parents[1:]) # 그룹 set해서 몇개 나오는지 확인
total_cost = 0 # 총 합계
for i in group:
# 각 그룹별 가장 적게 드는걸 뽑아야함
part_cost = 1e9
for minn in result_dict[i]:
part_cost = min(part_cost, A[minn][1])
total_cost += part_cost
# 초과하면 끝냄
if total_cost > part_cost:
print("Oh no")
exit()
# 다 통과했음
print(total_cost)
정답 코드
import sys
n, m, k = map(int, sys.stdin.readline().split())
# 비용기준 정렬
A = [0] + [cost for cost in list(map(int,sys.stdin.readline().split()))]
# 처음 부모는 자기 자신
parents = [i for i in range(n+1)]
# 제일 위 부모 찾기
def find(x):
# 자기 자신이 부모가 아니면
if x != parents[x]:
#부모의 부모를 찾아야함
parents[x] = find(parents[x])
return parents[x]
# 작은 비용기준으로 union 해줌
def union(a, b):
a = find(a)
b = find(b)
if A[a] < A[b]:
parents[b] = a
else:
parents[a] = b
# 누가 더 작은 지 찾아봄
for i in range(m):
v, w = map(int, sys.stdin.readline().split())
# 부모 찾기
# 합쳐야함 원래는 작은수로 합치지만, 이 문제에선 작은 비용 기준으로 해야한다.
union(v, w)
ans = 0
for idx, res in enumerate(parents):
if idx == res:
ans += A[idx]
if ans <=k:
print(ans)
else:
print("Oh no")
ans = 0
for idx, res in enumerate(parents):
if idx == res:
ans += A[idx]
if ans <=k:
print(ans)
else:
print("Oh no")이 부분이 중요하다.
parents 에는 작은 비용 기준으로 되어있다. 예를들면
5 3 20
10 10 20 20 30
1 3
2 4
5 4
> [0, 1, 2, 1, 2, 2]이렇게 되어 있으므로 enumerate로 돌려주어 인덱스랑 parents 값이랑 같으면 친구비용을 지불한것이므로
같을때 ans에 더해주면 된다.
댓글