문제 링크 https://www.acmicpc.net/problem/7453 문제 요약 길이가 \(N\)인 네 개의 배열이 주어진다. 이 때 네 개의 배열에서 각각 한개의 수를 뽑아 더했을 때 이 합이 0이 되는 경우의 수를 구하는 문제다. 문제 풀이 일단 모든 경우를 전부 보면 \(O(N^4)\)이기 때문에 시간초과가 나기 때문에 다른 방법이 필요하다. 우선 네 개의 배열 \(A\), \(B\), \(C\), \(D\)이 있다. 이 때 \(A\)와 \(B\)의 가능한 모든 합을 저장한 배열을 \(X\), \(C\)와 \(D\)의 가능한 모든 합을 저장한 배열을 \(Y\)라고 하자. 이 때 \(X\)에서 어떠한 수 한개를 뽑고, \(Y\)에서 어떠한 수 한개를 뽑아 이 수가 \(0\)이 된다고 생각을 해..
문제 링크 https://www.acmicpc.net/problem/1090 문제 요약 \(N\)개의 점이 주어진다. 이 때 적어도 한개의 점이 한 점위에 있도록 하기위해 움직이는 최소 횟수 , 적어도 두 개의 점이 한 점위에 있도록 하기위해 움직이는 최소 횟수, ... 적어도 \(N\)개의 점이 한 점위에 있게 하기위해 움직이는 최소 횟수를 구하는 문제다. 문제 풀이 모든 점을 모으는 것이 아니라는 것이 이문제를 어렵게 만드는 요소 중 하나다. 하지만 모든 점을 모으는데 있어 최선의 선택은 \(x\)좌표들의 중앙값, \(y\)좌표들의 중앙값으로 모이는게 최선이라는 생각을 살짝 변형하면 쉽게 풀 수 있다. (\(N\)개의 점을 모두 모으는데 왜 중앙값이 최선이냐에 대해서는 완벽하게 증명을 하진 못하겠다...
문제 링크 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번으로 ..
문제 링크 https://www.acmicpc.net/problem/2271 문제 요약 자연수로 이루어진 크기 \(N\)인 배열 \(A\)가 주어진다. 이 때 \(1\leq P\ \lt\ Q\ \lt\ R\ \lt\ S\ \leq\ N\)을 만족하는 \(P\), \(Q\), \(R\), \(S\)에 대해 아래 두가지 수식이 만족하는 경우가 있는지 찾는 문제다. 1. \(A[Q]\ \lt\ A[S]\ \lt\ A[P]\ \lt\ A[R]\) 2. \(A[Q]\ \gt\ A[S]\ \gt\ A[P]\ \gt\ A[R]\) 문제 풀이 우선 2번 경우는 생각하지 말고 1번 경우만 생각해 보도록 하자. \(i\lt j\) 인 임의의 \(i\), \(j\)를 선택했다고 하자. 만약 \(A[i] \lt A[j]\)를..
여기를 클릭해 주세요. 문제 링크 https://www.acmicpc.net/problem/3136 문제 요약 문제에서 주어진 방향대로 선을 그어나갔을 때 생기는 평면의 개수를 출력하는 문제. 문제 풀이 이 문제를 처음 본다면 당황할 수 있다. 언제 공간이 생기는지 아는것도 힘들 뿐더러 그걸 알았다고 하더라도 공간을 어떻게 세어야 할지 막막하기 때문이다. 하지만 정수 좌표를 버텍스라고 생각하고, 선들을 엣지라고 생각한다면 그래프에서의 평면의 개수를 찾는 문제로 치환이 된다. 일반적으로 그래프에서 평면의 개수를 찾는것은 어렵지만 선을 그어서 생기는 그래프는 평면그래프 라는것을 깨닫는 순간 문제는 매우 쉬워진다. 평면그래프에는 아래와 같은 공식이 있다. \(V\ -\ E\ +\ F\ =\ 2\) \(V\)은..
문제 링크 https://www.acmicpc.net/problem/9935 문제 요약 문자열 \(A\), \(B\)가 주어진다. \(B\)는 \(A\)안에서 연쇄적으로 사라질 때 최종적으로 남은 문자열이 무엇인지 출력하는 문제다. 문제 풀이 문자열이 연쇄적으로 사라진다는 점에 착안해서 \(A\)문자열을 앞에서부터 한 글자씩 답 문자열에 추가해 가면서 끝에서 \(B\)와 매칭이 되는가를 매번 확인해 준다. 매번 확인하면 시간내에 들어올까 하는 의문이 생길수도 있다. 하지만 \(A\)의 길이가 \(10^6\)데 비해 \(B\)의 길이는 최대 \(36\)밖에 안되기 때문에 매우 빠른속도에 통과하는것을 확인할 수 있다. 시간복잡도는 \(O(|A||B|)\)이다. 소스 코드 #include #include in..
여기를 클릭해 주세요. 문제 링크 https://www.acmicpc.net/problem/2841 문제 요약 기타는 총 6개의 줄로 이루어져 있으며 높은 플랫을 누르면서 낮은 플랫을 동시에 누르고 연주가 가능하지만 낮은 플랫을 눌러 연주를 해야하는데 이 때 높은 플랫이 눌려 있으면 안된다. 외계인이 연주할 곡의 음 순서가 들어올 때 손을 움직이는 횟수를 최소화 하고 싶다 문제 풀이 외계인이 각각의 손을 움직여야 할지 말아야 할지 모든 경우를 탐색해 보는것은 불가능하다. 하지만 잘 생각해 본다면 그 순간에 선택을 해야할지 그리디하게 결정할 수 있다. 우선 한개의 줄에 \(x \lt y\lt z\) 인 음이 있다고 생각을 해 보자. 이 때 연주하는 경우의 수는 크게 두가지로 나눠서 생각을 해볼 수 있다. ..
여기를 클릭해 주세요. 문제 링크 https://www.acmicpc.net/problem/6135 문제 요약 \(N\)개의 정점으로 이루어진 가중치가 있는 방향 그래프가 주어 진다. 그 뒤 \(Q\)개의 쿼리가 주어지는데 각각의 쿼리마다 두 개의 수 \(u\), \(v\)가 주어진다. 각 쿼리에 대해서 구해야 하는 값은 아래와 같다. \(u\), \(v\)로 가는 경로를 하나 선택했을 때 그 경로에 있는 엣지들의 무게들 중 가장 무거운 값이 있다고 하자. 이 값을 최소화 시키는 경로를 하나 찾는게 문제다. 실제 경로는 찾을 필요가 없고 최대중에 최소의 값만 찾으면 되기 때문에 쉽게 해결할 수 있다. 문제 풀이 \(D[u][v]\) = \(u\)에서 \(v\)로 가는 경로 중 만나는 엣지의 무게의 최대의..
여기를 클릭해주세요. 문제 링크 https://www.acmicpc.net/problem/10546 문제 요약 \(N\)개의 이름이 차례대로 주어진다. 그 뒤 \(N\)개의 이름 중 \(N - 1\)개가 차례대로 다시 주어진다. 이 때 다시 주어지지 않은 이름 한개를 찾는 문제다 문제 풀이 \(N\)이 최대 \(10^5\)이긴 하지만 한 이름의 길이가 최대 20밖에 안되기 때문에 \(map\)을 사용해 쉽게 해결할 수 있다. 한가지 주의할 점은 이름이 같은 사람이 존재하기 때문에 동일한 이름의 수를 세어주어야 한다. 소스 코드 더보기 #include #include #include using namespace std; map cnt; int n; char str[22]; int main() { scanf..
