문제 링크 https://www.acmicpc.net/problem/11670 문제 요약 \(N\)개의 줄에 걸쳐 \(A_i\)와 \(B_i\)가 주어진다. 이 때 각각의 \(A_i\)와 \(B_i\)에 대해 \(+,-,*\)중 하나를 선택해서 나온 결과를 모두 다르게 하고 싶다. 이렇게 연산자들을 선택하는게 가능한지, 가능하다면 어떻게 선택해야 하는지 출력하는 문제다. 문제 풀이 \(N\)이 최대 \(2,500\)개가 들어오기 때문에 완전탐색으로는 불가능하다. 우리는 모든 계산의 결과가 유니크해야하다는 것에 주목할 필요가 있다. \(A_i\)와 \(B_i\)의 쌍을 하나의 정점으로 생각하고 \(+,-,*\)한 결과들에 간선을 연결해 보자. 예제 입력을 그래프로 모델링하면 아래와 같은 결과가 나온다. 그..
문제 링크 https://www.acmicpc.net/problem/13344 문제 요약 수식이 주어졌을 때 주어진 수식들이 일관성이 있는지 혹은 모순이 있는지 찾아내는 문제다. 문제 풀이 수식은 크게 두가지 종류가 존재한다. 1. \(u = v\) : \(u\)와 \(v\)는 같다 2. \(u \gt v\) : \(u\)가 \(v\)보다 크다 만약 1번 수식이 없다고 생각을 해보자. 1번 수식이 없고 2번 수식만 있을 때 주어진 수식들이 일관성이 있는지 없는지 어떻게 판단을 할 수 있을까? \(u\)와 \(v\)가 나오고 \(\gt\)가 화살표 처럼 생겼으므로 \(u\)에서 \(v\)로 향하는 방향 그래프를 만들어 보자. 이 때 만약 \(Cycle\)이 있으면 어떻게 될까? \(Cycle\)이 존재하도..
문제 링크 https://www.acmicpc.net/problem/1208 문제 요약 크기 \(N\)인 집합이 주어진다. 이 때 부분집합의 합이 \(S\)가 되는 경우의 수를 구하는 문제다. 문제 풀이 \(N\)이 최대 40이기 때문에 완전탐색으로는 안된다. 따라서 다른 방법이 필요하다. 이런 경우에는 왼쪽 절반과 오른쪽 절반의 모든 경우의 수를 각각 구하고 이분탐색을 통해 이 경우의 수를 합쳐나갈 수 있다. 크기 \(N\)인 집합을 왼쪽부터 \(N \above 1pt 2\)개의 완전탐색 경우의 나머지 오른쪽의 완전탐색 경우를 다 구해 놓는다. 이 때 왼쪽의 경우의 수와 오른쪽 경우의 수를 어떻게 합쳐야 할까? 왼쪽의 경우 중 가능한 한가지 합이 \(x\)라고 가정을 해 보자. 그렇다면 오른..
문제 링크 https://www.acmicpc.net/problem/1867 문제 요약 \(N*N\)격자판위에 돌맹이들이 놓여져 있다. 한번의 작업으로 한개의 행이나 한개의 열에 있는 돌멩이를 모두 제거할 수 있다. 이 때 최소 몇번의 작업을 해야 격자판 위에 있는 돌멩이를 모두 제거할 수 있는지 구하는 문제다. 문제 풀이 처음 이 문제를 본다면 \(greedy\)로 접근을 하기 쉽다. 하지만 그렇게 접근을 시작하는 순간 문제는 미궁으로 빠지게 된다. 그렇다면 어떻게 접근을 해야할까? 우선 아래와 같은 격자판이 있다고 가정을 해보자. 위 격자판을 그래프로 생각해보자. 정점은 각각의 열과 행이고 돌멩이가 있는 칸은 열과 행을 잇는 간선이라고 생각을 한다. 그렇다면 그래프는 아래와 같이 그려진다. 만약에 \..
문제 링크 https://www.acmicpc.net/problem/2843 문제 요약 \(N\)개의 정점가 \(N\)개의 간선을 가지는 방향그래프가 주어진다. 각각의 정점은 최대 한개의 나가는 간선을 가질 수 있다. 이 때 두 가지의 쿼리를 처리해야 한다. 첫 번재 쿼리는 \(x\)번 정점에서 나가는 간선을 지우는 것이도 두 번째 쿼리는 \(x\)번 정점에서 나가는 간선을 따라 계속해서 움직일 때 마지막으로 도착하는 정점이 어디인지, 만약 영원히 끝나지 않는다면 영원히 끝나지 않는다고 출력을 해야 한다. 문제 풀이 연결된 그래프에서 간선을 지워서 두개의 분리된 그래프로 만드는 작업은 생각보다 어려운 일이다. 하지만 반대로 두개의 분리된 그래프를 하나로 합쳐 새로운 그래프를 만드는 작업은 꽤 쉬운 일이다..
문제 링크 https://www.acmicpc.net/problem/1704 문제 요약 \(N*M\)크기의 격자판이 주어진다. 이 격자판에는 0또는 1이 적혀져 있는데 \((x, y)\)를 누르면 \((x, y)\)를 포함 상, 하, 좌, 우 이렇게 다섯개 칸의 상태가 토글된다. 최소한의 연산 횟수를 통해 격자판의 모든 수를 0으로 만드는것이 목표다. 최소한의 연산 횟수를 가지는 것이 여러개라면 사전순으로 빠른 답을 출력한다. 문제 풀이 상태가 토글된다는 것이 이 문제를 푸는 핵심이다. \((x, y)\)를 누르면 해당 칸과 주위 네 방향이 같이 토글된다. 이 때 동일한 칸을 두 번 이상 누를 필요가 없다. 왜냐하면 두번 이상 누르는 순간 기존의 상태와 똑같아 지거나 한번 누른 상태와 똑같아 지기 때문이..
문제 링크 https://www.acmicpc.net/problem/6233 문제 요약 \(N\)마리의 소들이 일렬로 서 있다. 이 소들은 앞을 보고 있거나 뒤를 보고 있다. 이 때 이 소들에 대해서 다음과 같은 연산을 할 수 있다. 1. 특정 길이 \(L\)을 정한다. 이 값은 변하지 않는다. 2. 정확히 \(L\)마리의 연속된 소들의 상태를 반전시킬 수 있다. 3. 상태를 반전시킨다는 것은 앞을 보고 있는 소는 뒤를 보고, 뒤를 보고 있는 소들은 앞을 보는것이다. 2번 연산을 최소한으로 사용해 모든 소들을 앞을 보게 하는것이 문제다. 만약 최소한의 연산 횟수를 가지는 \(L\)이 여러가지면 그중에 작은것을 출력한다. 문제 풀이 우선 문제를 간단하게 만들기 위해 \(L\)이 정해져 있다고 생각을 해보자..
문제 링크 https://www.acmicpc.net/problem/2196 문제 요약 \(B\)자리의 2진수 \(E\)개가 주어진다. 이제 이진수를 두개씩 선택해서 XOR을 진행한다. 이 과정에서 만들어지는 수 또한 선택할 수 있다. 이렇게 해서 만들 수 있는 이진수들 중 이진수 \(S\)와 해밍거리가 가장 가까운 수를 출력하는 문제다. 문제 풀이 이 문제를 어렵게 만드는 요소 중 하나는 XOR과정에서 만들어진 수 또한 XOR연산에 사용할 수 있다는 점이다. 하지만 XOR의 특징을 잘 생각해 본다면 이 문제를 쉽게 해결할 수 있다. \(A\), \(B\), \(C\), \(D\) 네 개의 이진수가 있다고 가정하자. \(A \oplus B\)를 통해 \(X\)를 만들고 \(C \oplus D\)를 통해 ..
문제 링크 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\)이기 때문에 빠른 풀이를 생각해야 한다. 결론부터 얘기하면 이 문제..
