본문 바로가기

Platinum18

BOJ 8872 : 빌라봉 문제 링크 : https://www.acmicpc.net/problem/8872 문제를 요약하자면, 여러 개의 독립된 트리들이 주어진 포레스트가 주어진다. 이 때, 각 트리들 사이에 간선을 추가하여 완성된 전체 트리의 지름을 최소화시켜야 한다. 트리의 지름과 반지름, 중심에 대한 이해가 있다면 쉽게 풀 수 있다. 우선, 예제의 그림을 통해 관찰해보자. 새로운 간선을 0 번 노드에 연결하면, 최대 거리가 4 + 4 + 2 = 10 이 된다. 만약 새로운 간선을 다른 곳에 연결한다면, 최대 거리가 더 작아지지 않을까? 아래 그림을 보자. 8번 노드(또는 2번 노드) 를 선택하면 최대 거리가 6 이다. 더 효율적인 것이다. 따라서, 우리는 각 트리 내에서 같은 트리 내의 정점 간의 최대 거리가 최소인 노드를 .. 2022. 9. 13.
BOJ 1146 : 지그재그 서기 문제 링크 : https://www.acmicpc.net/problem/1146 1 ~ N 의 순열 중에서, 인접한 두 수의 대소관계가 번갈아가면서 나타나는 순열의 가짓수를 세는 문제다. 우선 관찰을 해보자. 만약 첫 번째 수가 두 번째 수보다 작다면, 수열은 대략 아래와 같은 개형을 가질 것이다. 즉 1 ~ N 까지의 수들 중 서로 다른 두 수 a, b (a < b) 를 선택하여 위 처럼 배치 가능하다. 여기서 중요한 사실은, a 는 이제 이후의 수열에 아무 영향을 안 준다는 것이다. 이제는 b가 처음이라고 봐도 되는 것이다. a, b 를 선택하여 배치했으니, 남은 N-2 개의 수들을 살펴보자. b 의 다음 수로 가능한 수는 몇 개일까? b 보다 작아야하므로 1 ~ b-1 인데, 이 중에서 a 는 이미.. 2022. 9. 13.
BOJ 19544 : 함수 복원 문제 링크 : https://www.acmicpc.net/problem/19544 함수의 값이 f(x) = y 라면, x -> y 로 이어주는 방향그래프의 가짓수를 구하는 문제다. 우선 중요한 점은 함수기 때문에, 모든 노드의 outdegree == 1 이라는 사실이다. indegree 는 얼마든지 커질 수 있고 0 일 수도 있지만, outdegree 만큼은 다 1 이어야 한다. 이 문제의 아이디어는 BOJ 6991 계통트리와 유사하게 떠올렸다. (계통트리 풀이) 예제를 보니 갈 수 있는 정점들이 완전히 일치하는 노드들이 나왔다. 계통트리에서는 이런 노드들이 같은 부모를 공유한다는 관찰을 해야 했다. 조금만 생각해보면, 이 문제에서는 이 노드들은 같은 사이클 속에 있다는 것을 알게 된다. 예제 1을 예시.. 2022. 9. 6.
BOJ 20131 : 트리 만들기 문제 링크 : https://www.acmicpc.net/problem/20131 관찰 1 처음 이 문제를 봤을 때 생각이 잘 안 나서, 노드 개수가 4개인 트리를 다 그려봤다. 각각의 트리에 대해 문제에서 요구하는 순열을 구했는데, 전부 다르게 나왔다. 즉, 트리가 다르면 순열이 다르다는 것을 알게 됐다. 관찰 2 1번 예제의 입력이 9 4 4 5 4 4 6 이었다. 4가 왜 4번 등장했는지, 9, 5, 6 은 왜 1번 등장했는지, 나머지 1, 2, 3, 7, 8 은 왜 안 등장했는지 고민했다. 예제의 트리를 그려보고 등장횟수가 같은 정점들의 공통점을 찾아봤다. 그 결과, 1, 2, 3, 7, 8 은 말단노드이기에 한 번도 등장하지 않았다는 것을 알게 되었다. 이제는 1번만 등장한 9, 5, 6 을 살.. 2022. 9. 5.
BOJ 2261 : 가장 가까운 두 점 문제 링크 : 문제는 정말 단순하다. N 개의 점이 2차원 좌표평면에 있으면, 가장 가까운 두 점 사이의 거리를 구하면 된다. 단, N 제한이 최대 10만이기 때문에 O(N2) 풀이는 불가능하다. 시간을 줄이기 위해서, 우선 N2 개의 쌍들 중 답이 될 가능성이 없는 것을 생각해보자. 현재까지 구한 답이 10 이라면, x 좌표가 10 이상 차이 나는 쌍들은 답을 절대 갱신시킬 수 없다. 따라서, 현재까지 구한 가장 가까운 거리가 유용한 정보가 될 것이다. 위 논리에서 이어지는 생각으로, 우선 점들을 x 좌표 기준으로 정렬을 하자. 물론 왼쪽부터 차례대로 스위핑을 해도 되지만, 이 풀이에서는 점들을 반으로 가를 것이다. 즉 N 개의 점들을 왼쪽 N/2 개, 오른쪽 N/2 개로 분리한 후 답을 찾을 것이다... 2022. 8. 31.
BOJ 3830 : 교수님은 기다리지 않는다 문제링크: 실시간으로 x, y, z 가 입력된다. 이 말은 x 보다 y 가 z 만큼 무겁다는 뜻이다. 중간중간 쿼리 a, b 가 입력된다. 이 때 우리는 a 보다 b 가 얼마나 무거운지 출력해야 한다. 샘플은 최대 10만개, 쿼리와 무게관계도 최대 10만개 입력된다. 이 문제는 개인적으로 굉장히 좋은 문제라고 생각한다. 우선 Union-Find 와 관련있다는 것은 금방 관찰할 수 있다. x y z 가 입력이 되면, x 와 y 는 서로 무게 차이를 알아낼 수 있는 관계가 된다. 그 말은, x 와 서로 무게 차이를 알아낼 수 있는 샘플은 y 와도 서로 무게 차이를 알아낼 수 있다는 것이다. 따라서 쿼리 a, b 가 입력됐을 때, a 와 b 가 연결되지 않았으면 UNKNOWN 이 답이다. 하지만 이 문제는 단.. 2022. 8. 27.

티스토리툴바