문제 링크 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\)이 존재하도..
2016/11/15
문제 링크 https://www.acmicpc.net/problem/1208 문제 요약 크기 \(N\)인 집합이 주어진다. 이 때 부분집합의 합이 \(S\)가 되는 경우의 수를 구하는 문제다. 문제 풀이 \(N\)이 최대 40이기 때문에 완전탐색으로는 안된다. 따라서 다른 방법이 필요하다. 이런 경우에는 왼쪽 절반과 오른쪽 절반의 모든 경우의 수를 각각 구하고 이분탐색을 통해 이 경우의 수를 합쳐나갈 수 있다. 크기 \(N\)인 집합을 왼쪽부터 \(N \above 1pt 2\)개의 완전탐색 경우의 나머지 오른쪽의 완전탐색 경우를 다 구해 놓는다. 이 때 왼쪽의 경우의 수와 오른쪽 경우의 수를 어떻게 합쳐야 할까? 왼쪽의 경우 중 가능한 한가지 합이 \(x\)라고 가정을 해 보자. 그렇다면 오른..
