220825 문제 풀이 기록

G5 | 14699 - 관악산 등반

걸린 시간: 약 15분 (부정확)

체감 난이도: G5 ~ G4 사이 그 어딘가 애매한 지점

시도 횟수: 1회

풀이 쓸 의향: 下

풀이:

높이 있는 노드부터 차례대로 내려오면서 최대값 저장하기.

여담: 친구가 암만봐도 골드 5 아닌것같다고 해서 풀어본 문제.

솔직히 아이디어 자체는 G5가 맞는데 그래프기도 하고 이런저런 구현방법 잘 모르면 시간 끌릴수도 있겠다 싶어서 G4로 난이도 기여함.

 

 

P5 | 2463 - 비용

걸린 시간: 45분

체감 난이도: P4 하위권

시도 횟수: 2회

풀이 쓸 의향: 中

풀이:

비용 큰 간선부터 차례대로 간선 연결하면서, disjoint set으로 간선이 연결하는 그래프의 크기 고려하면서 정답값 더해주기.

여담: disjoint set 구현할 때 두 root값(그래프 크기값)을 곱하는 부분이 있었는데, root값을 int로 둬서 한번 틀림.

솔직히 처음 봤을때 바로 MST(Maximum)이 떠올랐는데, 실상 풀이는 MST를 안쓰는게 더 편해서 오히려 생각이 더 꼬였던 것 같다.

(풀이 메모)

가중치가 가장 작은 / 큰 간선은 몇 번 제거될까

작은 간선들을 보면?
가령 가중치가 2인 간선은 그냥 뭘 해도 다 없어지네?
!
MST
MST...가 맞나
Maximum?
Maximum spanning tree를 구성하자.

그럼 예제 그래프에서 남는 간선들이?
15 10 6 5 4가 된다
제거되는건 2, 3 <-- 얘들은 모든 두 정점 (u, v)에 대해 그냥 계속 없어지니까, N(N-1)/2번 없어진다
이제 작은것부터 보자
4도 뭘 해도 끊어진다
5는? (4 끊을때 5번 노드가 끊기므로) 5번 노드가 들어간 거 빼고는 다 끊어진다
6은? (5 끊을때 4번 노드가 끊기므로) 4번 노드가 들어간 거 빼고는 다 끊어진다
10은? (6 끊을때 그래프가 1-2, 3-6으로 나뉘므로) 

음
그래프가 나뉘는데, 각 그래프의 크기에 대해
어떤 한 그래프에서 다른 그래프로 연결하는 개수만큼..? 쫌 복잡하네요,,, 으엑

(1, 2) : 10 이하 다 끊김
(1, 6) : 6 이하 다 끊김
(1, 3) : 6 이하 다 끊김
근데 이렇게하면... N^2이잖아...

모든 그래프에서, 각 그래프 크기를 x라 하면,
sum(x(x-1)/2);
이게 깔끔하네
4:15
5:10
6:6
10:2
15:1

9*15 + 50 + 36 + 20 + 15



근데 구현을 어케함 이걸
uf 쓰기 싫은데
아니 uf 써도 시간 안에 되나
끊는거보단 잇는게 쉬우니깐...
큰거부터 이어볼까

!!

큰거부터 이어서 조지자
연결됐을 때, (x + = sz[s]*sz[e]), ans += v[node] * x;

ㄱㄱㄱㄱㄱㄱ
근데.. 그럼 사실 MST 필요없는거 아닌가
으익..!!!!
이미 연결되어 있었다면 x 증가 안시키고, 연결 안되어있었을 때만 증가시키게 하면 될듯
ㄱㄱ