문제 링크 https://www.acmicpc.net/problem/1090 문제 요약 \(N\)개의 점이 주어진다. 이 때 적어도 한개의 점이 한 점위에 있도록 하기위해 움직이는 최소 횟수 , 적어도 두 개의 점이 한 점위에 있도록 하기위해 움직이는 최소 횟수, ... 적어도 \(N\)개의 점이 한 점위에 있게 하기위해 움직이는 최소 횟수를 구하는 문제다. 문제 풀이 모든 점을 모으는 것이 아니라는 것이 이문제를 어렵게 만드는 요소 중 하나다. 하지만 모든 점을 모으는데 있어 최선의 선택은 \(x\)좌표들의 중앙값, \(y\)좌표들의 중앙값으로 모이는게 최선이라는 생각을 살짝 변형하면 쉽게 풀 수 있다. (\(N\)개의 점을 모두 모으는데 왜 중앙값이 최선이냐에 대해서는 완벽하게 증명을 하진 못하겠다...
2016/11/10
문제 링크 https://www.acmicpc.net/problem/1814 문제 요약 크기가 \(N\)인 트리가 주어진다. 이 트리의 정점들을 \(M\)가지의 색으로 칠하려고 하는데 각각의 색들은 색을할 할 때 비용이 든다. 또한 인접한 정점은 서로 색이 달라야 한다. 제약조건을 지키면서 모든 정점들을 칠할 때 드는 최소 비용을 구하는 문제다. 문제 풀이 주어지는 입력이 트리이기 때문에 \(dp\)로 쉽게 풀릴것 같은 생각이 든다. 아래와 \(dp\ table\)을 생각해보자. \(dp[here][color]=\ \)\(here\)를 \(color\)로 색칠하고 \(here\)의 \(subtree\)를 색칠하는데 드는 최소 비용 이 식은 어떻게 채워질 수 있을까? 이식은 아래와 같을 것이다. \(dp[..
문제 링크 https://www.acmicpc.net/problem/1787 문제 요약 문제가 이해를 하기 조금 힘들지만 결국 하는말은 다음과 같다. 어떠한 문자열 \(X\)가 있다고 가정을 하자. 이 때 \(X\)의 \(Prefix\)와 \(Suffix\)를 구하는데 이 때 빈 문자열이면 안되고 서로 동일한 길이여야 한다. 이렇게 뽑았을 때 \(Prefix\)와 \(Suffix\)가 같은 0이 아닌 가장 작은 길이를 구한다음에 \(X\)의 길이에서 뺀뒤 이 값을 답에 누적한다. 이러한 과정을 문자열 \(S\)가 주어지면 \(S\)의 모든 \(Prefix\)에 대해서 반복한다. 문제 풀이 주어지는 문자열 \(S\)의 길이가 \(10^6\)이기 때문에 빠른 풀이를 생각해야 한다. 결론부터 얘기하면 이 문제..
문제 링크 https://www.acmicpc.net/problem/13352 문제 요약 문제는 정말 간단하다. \(N\)개의 2차원 정수 좌표가 주어진다. 모든 좌표들이 최대 두개의 직선위에 놓일 수 있는가, 없는가를 판단하는 문제다. 문제 풀이 이 문제를 풀 수 있는 솔루션은 여러가지가 존재하지만 재미있는 방법 한가지를 소개하려 한다. 아래와 같은 프로그램을 상상해보자. 1. \(N\)개의 점중에 서로 다른 두 개의 점을 임의로 뽑자. 이 때 임의의 두 점을 이어 만든 직선을 \(A\)라고 하자. 2. 직선 \(A\)위에 존재하지 않는 점들이 새로운 직선 \(B\)위에 놓일 수 있는지 확인한다. 3. 만약 가능하다면 최대 두개의 직선으로 모든 좌표를 덮을 수 있다. 4. 만약 불가능 하다면 1번으로 ..
