![]()
문제 링크 https://www.acmicpc.net/problem/6241 문제 요약 \(N\)마리의 소와 \(F\)개의 음식, \(D\)개의 음료가 주어진다. 각각의 소들은 식성이 다 다르기 때문에 좋아하는 음료, 음식들이 전부 다 다르다. 소들은 자신이 좋아하는 음식들 중 한개와 자신이 좋아하는 음료들 중 한개를 동시에 먹을 때 행복하다고 느낀다. 모든 음식과 음료들은 한 소에게만 나눠줄 수 있을 때 행복한 소의 수를 최대로 만드는 문제다. 문제 풀이 얼핏 보면 이분 매칭과 흡사해 보일 수 있다. 하지만 이 문제는 소에게 음료와 음식을 동시에 할당해 줘야 하기때문에 이분 매칭으로는 풀 수 없다. 그렇다면 조금은 다른 풀이를 생각해야 한다. 이 문제에서는 소를 정 중앙에 두고 왼쪽에는 음식, 오른쪽에..
![]()
문제 링크 https://www.acmicpc.net/problem/11670 문제 요약 \(N\)개의 줄에 걸쳐 \(A_i\)와 \(B_i\)가 주어진다. 이 때 각각의 \(A_i\)와 \(B_i\)에 대해 \(+,-,*\)중 하나를 선택해서 나온 결과를 모두 다르게 하고 싶다. 이렇게 연산자들을 선택하는게 가능한지, 가능하다면 어떻게 선택해야 하는지 출력하는 문제다. 문제 풀이 \(N\)이 최대 \(2,500\)개가 들어오기 때문에 완전탐색으로는 불가능하다. 우리는 모든 계산의 결과가 유니크해야하다는 것에 주목할 필요가 있다. \(A_i\)와 \(B_i\)의 쌍을 하나의 정점으로 생각하고 \(+,-,*\)한 결과들에 간선을 연결해 보자. 예제 입력을 그래프로 모델링하면 아래와 같은 결과가 나온다. 그..
