BOJ 32126 돌고래 사진

문제 요약
1번부터 N번까지의 돌고래가 있고, 이 돌고래는 각자 자신의 서식지에서 살고 있다. 돌고래들은 가끔씩 자신의 서식지에서 묘기를 부리고, 이 묘기를 부리는 시각이 N*K 크기의 행렬 M으로 주어진다(N은 400이하, M은 800이하). 만약 M_ij가 1이라면 i번 돌고래가 시각 j에 묘기를 부린다는 뜻이다. 이 돌고래들의 묘기를 사진으로 찍으려 한다. 각 시각 t에 대해서(t는 1이상 K이하), 1. 카메라가 없는 서식지를 골라서 카메라를 설치하거나, 2. 이미 카메라가 설치된 서식지 중 하나를 골라 돌고래가 묘기를 부리는 모습을 찍을 수 있다. 묘기를 촬영할 수 있는 돌고래의 최대 마리 수를 구하여라.

풀이
토요일에 열린 LGCPC C번 문제였고, 이 문제의 서브태스크 3번이 본선 진출을 가르는 문제가 될듯하다. 다행히 서브태스크 3번을 긁는데 성공하여 본선에 진출할 수 있을 것 같다.

서브태스크 3번은 N까지의 시각에서 돌고래가 묘기를 한번도 부리지 않는 행렬만 주어진다. 따라서 그냥 모든 서식지에 카메라가 설치되어 있는 것으로 생각해도 무방하다. 다음과 같이 그래프를 모델링하면 플로우로 해당 서브태스크를 해결하고 36점을 긁을 수 있다.

S : 소스
1~N : 각 돌고래를 나타내는 정점
N+1~N+K : 각 시각을 나타내는 정점
T : 싱크

1. 먼저 소스와 각 돌고래 사이를 용량이 1인 간선으로 잇는다.
2. M_ij=1이라면 i번 돌고래와 j번 시각 사이를 용량 1인 간선으로 잇는다.
3. 각 시각과 싱크 사이를 용량 1인 간선으로 잇는다.

풀태스크는 어렵다. 저 풀이를 짜고 제출해서 36점을 긁은 다음에 대회가 끝날 때까지 고민을 했지만 결국 방법을 떠올리지 못했다. 카메라를 설치하는 행동을 어떻게 그래프 모델링으로 나타내야 할지 전혀 감도 안 왔다.

끝나고 풀이를 들었을 때는 머리를 한대 얻어 맞은 기분이었다. 핵심은 카메라를 설치하는 것을 행동으로 생각하는 것이 아니라, 이 자체를 'i번 시각까지 촬영할 수 있는 최대 돌고래는 최대 i/2개 뿐이다'라는 조건으로 해석해야 한다.

저 해석이 끝나면 문제는 허무할 정도로 쉽게 풀린다. 시각과 싱크 사이에 K/2개의 정점을 추가해서 저 조건을 반영해주면 끝난다.

플로우를 못해서 못 푼 줄 알았는데 그냥 PS를 못해서 못 푼 거였다. 지금 생각해보니 그렇게 어려운 발상도 아닌데 못 떠올린 게 아쉽다. 이 부분은 반성을 하고 별개로 LG가 플로우 문제를 상당히 좋아하는 것 같으니 삼성 대회가 끝나면 LG 대회 대비용으로 플로우 특훈을 해보자. 내가 플로우를 못하는 것도 맞기 때문에...