전체 글 (33) 썸네일형 리스트형 [ICPC 본선 대비 뇌셋] Day 8 백준 8987번 수족관 3 www.acmicpc.net/problem/8987 8987번: 수족관 3 입력의 첫 줄은 수족관의 경계에 있는 꼭짓점의 개수 N(4 ≤ N ≤ 300,000)이 주어진다. N은 짝수이다. 수족관의 경계는 항상 꼭짓점 (0, 0)부터 시작한다. 그리고 마지막 꼭짓점은 (A, 0)의 형태로 끝난 www.acmicpc.net 그리디로 찾으면 된다. 제일 물이 많이 빠지는 것을 찾은 후, 그 다음에 물이 제일 많이 빠지는 것을 찾고, 그 과정을 반복한다. [증명] 제일 많이 빠지는 점을 S1이라고 하자. S1에서 물을 빼면 S1을 기준으로 양 옆으로 갈수록 수위가 높아진다. 그리고 이를 첫번째 수위라고 정의하자. 만약 S2, S3를 뺀 것이 S1, S2를 뺀 것보다 양이 많다고 가정.. [ICPC 본선 대비 뇌셋] Day 7 백준 4009번 순찰 www.acmicpc.net/problem/4009 4009번: 순찰 1부터 N까지 번호가 붙여진 N개의 마을과, 이들 마을을 모두 연결하는 N-1개의 도로가 있다. 각 도로는 정확히 두 마을을 연결하며, 임의의 마을로부터 다른 모든 마을까지 이들 도로들만 이용하�� www.acmicpc.net 왜인지 모르겠으나 점점 강해지는 느낌이 든다.. [관찰 1] 지름길을 하나 박으면, 두 끝 정점 사이의 최단 경로에 있는 도로는 한번만 이동해도 되며, 나머지 도로는 두번씩 지나가야 한다. [관찰 2] 지름길을 두개 박으면, 관찰 1과 비슷한 식으로 생각할때, 두 개의 최단 경로를 잡을 수 있고, 이들 중 중복되지 않는 도로는 한번씩만 이동해도 되고, 중복되거나 경로에 포함되지 않은 도로는 .. [ICPC 본선 대비 뇌셋] Day 6 백준 1868번 보물찾기 www.acmicpc.net/problem/1868 1868번: 보물찾기 첫째 줄에 n이 주어진다. (1≤n≤50,000) 이후 n-1개의 줄에는 각각 두 개의 숫자가 주어진다. a와 b가 주어졌다면, a번 방과 b번 방 사이에 복도가 있어 왕래할 수 있다는 의미이다. 방의 번호는 1번부 www.acmicpc.net 이 문제를 본지 1주일만에 풀이를 쓰는 것 같다. 방법은 대충 생각하고 있었는데 구체화가 너무 더뎌 푸는데 오래걸렸다. 여담이지만, 내 첫 루비를 장식하게 되었다. [시도 1] 트리의 지름일 것이다. --> 반례를 찾을 수 있다. [시도 2] centroid decomposition을 하면 될 것이다. --> 반례를 찾을 수 있다. 일반적인 그리디를 통해서 문제를 접.. 이전 1 ··· 6 7 8 9 10 11 다음