공작소

문제 링크 : https://www.acmicpc.net/problem/1477 풀이 과정처음 접근 방법은, 최대 길이 구간의 중간에 휴게소를 설치하는 아이디어였다. 예를 들면, n = 4, l = 700 이고휴게소 위치 :  100  200  500  600구간 길이 :  100  100  300  100  100일 때,최대 길이 구간인 200 ~ 500 중간에 휴게소를 설치하여휴게소 위치 :  100  200 (350) 500  600구간 길이 :  100  100  150  150  100  100 다음과 같이 최대 길이 구간을 찾고, 그 구간을 분할하는 걸 m번 반복할 생각이였다. 하지만 이 아이디어는 최적의 방법이 아니다. 중간 설치 아이디어 문제점 : 균일하게 나누는 것이 더 최적이다.예를 들..

문제 링크 : https://www.acmicpc.net/problem/5214 풀이 과정역 하나하나마다 간선을 연결하는 것은 너무 비효율적이다. 한 하이퍼튜브 안에서 모든 역은 연결되어 있기 때문이다.한 하이퍼튜브가 서로 연결하는 역의 개수 K의 최대 제한이 1000이므로, 각 하이퍼튜브마다 K(K-1) 개의 단방향 간선을 생성해야 하는 일이 발생한다. 한 하이퍼튜브 안에서 단번에 다른 하이퍼튜브로 갈 수 있는 방법이 필요하다.  바로 하이퍼튜브 정점을 따로 만드는 것이다. 하이퍼튜브 정점을 따로 만들면, 한 하이퍼튜브 안에 있는 역 정점들은 하이퍼튜브 정점 한 개를 거쳐서 바로 연결되고, 다른 하이퍼튜브 안에 있는 역 정점 또한 하이퍼튜브 정점을 거쳐서 바로 연결될 수 있다. 이 아이디어가 있으면, ..