문제 https://www.acmicpc.net/problem/10159 10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net 풀이 solved.ac 난이도: Gold 3 모든 두 정점 쌍 사이의 거리를 구하는 플로이드-와샬(Floyd-Warshall) 최단 경로 알고리즘을 조금 변형해서 푸는 문제. 플로이드 알고리즘은 두 정점의 최단 거리를 구하지만 만약 두 정점 사이의 경로가 없다면 dist의 초기화 값이 INF값이 그대로 남게 된다. 즉, adj[i][j]의 초기화 값이 그대로 남았다면..

문제 www.acmicpc.net/problem/2437 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓 www.acmicpc.net 풀이 solved.ac 난이도: Gold3 그리디 알고리즘 문제이지만 DP문제에서 많이 본 유형이라 문제 분류를 몰랐다면 DP로 접근했을 듯한 문제였다. 해당 문제의 그리디 알고리즘은 다음과 같다. 일단 추를 무게의 오름차순으로 정렬했다 가정하자. 지금까지 idx번째의 추까지 사용하여 만들 수 있는 무게들 중 가장 큰 것을 end_num라고 하자. 다음 추 idx+1를 추가적 이용하여 만들 수 있는 무게들은 0,1,..