[BOJ 7332] 편의점 알바

https://www.acmicpc.net/problem/7332

꼭 풀겠다는 마음에 번역부터 하고 1년이 지나고서야 풀이까지 찾아가면서 풀게 되었다.

처음 들었을 때는 정말 신기한 방법이다. 문제를 안 보고 들어온 사람은 뒤로 가는 것을 추천한다.

총 $k$명 이하의 아르바이트를 쓰는 만족하는 해가 있다고 하자. (일단 둬 보자: 파라매트릭 서치) 그 해를 $x[1..24]$이라고 둘 것이다; $x[i]$ $:=$ 고용하는 아르바이트 중 $(i-1)$시에 시작하는 사람의 수.

이제 $x$ 배열이 만족해야 되는 여러가지 조건식들을 써 보자.

$able[i] :=$ $(i-1)$시에 일을 시작할 수 있는 아르바이트생의 수, $need[i] :=$ $(i-1)$~$i$시에 필요한 아르바이트생의 수라고 둘 때,

1. $0 \le x[i] \le able[i] $

2. 모든 $8 \le i \le 23$에 대해, $need[i] \le \sum_{k=i-7}^i x[i] $

(3.은 2.가 자정을 걸칠 경우에 식을 다시 정리한 것일 뿐이다)

3. 모든 $0 \le i \le 7$에 대해, $need[i] \le \sum_{k=0}^i x[i] + \sum_{k=17+i}^{23} x[i] \le k - \sum_{k=i+1}^{i+16} x[i] $

정말 멋지게도, 모든 조건이 $x$의 연속한 몇 원소의 합의 범위를 제한하고 있다. 이 때 접두사 합인 $s[i] := \sum_{k=0}^{i-1} x[i] $ ($s[0]=0$이다!)를 정의해 주면 모든 제한이 두 $s$값의 차이에 대한 부등식으로 나타난다는 것을 알 수 있다!

1-1. $s[i-1] \le s[i]$

1-2. $s[i] \le s[i-1] + able[i]$

2. 모든 $8 \le i \le 24$에 대해, $s[i-8] \le s[i] - need[i] $

3. 모든 $0 \le i \le 7$에 대해, $s[i+16] \le s[i] + k - need[i] $

신기한 것은, 이제 이것을 그래프로 모델링할 수 있다는 것이다! $s[0] = 0$으로 두고 가능한 $s[1..24]$를 찾는 방법을 생각해봤을 때, 각 s값에 정점이 대응되는, 정점이 25개인 그래프를 만들 수 있다. 위의 모든 상관관계 "$s[i] \le s[j] + c$"를 $i$에서 $j$로 가는 가중치 $c$의 간선으로 생각하면, 0번째 정점에서 $i$번째 정점으로 가는 어떠한 거리(최단 거리가 아니여도 된다)보다도 $s[i]$가 크거나 같아야 하는 것이다. 상관관계에 의해서 무조건 성립한다. 따라서, 만들어진 그래프에서 길이가 양수인 사이클이 도달 가능하다면, 그런 해는 존재하지 않는 것이다. 상관관계를 따라가면 필요한 알바의 수가 무한대로 증가하게 되기 때문이다! 양의 사이클이 존재하는지, 또는 하지 않는지 판별하는 데에 Bellman-Ford 알고리즘이나 SPFA에서 음의 사이클 판별하는 방법을 거꾸로 사용하면 된다. (최장 거리를 갱신해가면서 하면 된다.)

설명이 난잡해진 것 같다. 결론만 요약하면 다음과 같다.

1. 파라매트릭 서치를 한다. 답은 0에서 n 사이일 것이다.

2. 0~24번의 정점이 존재하는 그래프를 만든다.

3. 위의 상관관계들에 따라 그래프를 만들고, 양의 사이클이 존재하는지 판별한다. (0으로 가는 길이가 0 초과인 거리가 존재하는지만 판별해도 된다.) 벨만 포드나 SPFA를 사용하면 된다.

이 문제 말고도, 구간 합 또는 값의 차의 조건을 주고 가능한 지 판별하는 문제는 대개 조건을 그래프로 모델링하여 풀 수 있다.