추석맞이 POI풀이: Canoes

문제 링크: https://www.acmicpc.net/problem/8094

문제 요약

w와 5이상 w이하의 숫자 n개가 주어진다. 이 숫자들을 몇 개의 그룹으로 묶을 건데, 각 그룹에는 최대 2개의 숫자가 들어갈 수 있고 그 두 수의 합은 w를 넘으면 안 된다. 또, 모든 숫자가 그룹에 포함되어야 한다. 이 때 가능한 한 최소 그룹 개수를 구하여라.

풀이

그리디한 접근 방법으로 풀 수 있다. 직관적으로, 제일 작은 숫자부터 숫자 k에 대해서 w-k이하인 숫자들 중에 제일 큰 걸 그 k와 묶어주면 답이 될 것이다 라는 생각을 할 수 있고(그렇게 해야 최대한 해당 한 그룹에 많이 넣을 수 있으니까), 그 생각대로 구현하면 AC를 받을 수 있다.

이런 그리디한 문제는 답 보다도 그 풀이의 정당성에 대한 증명이 더 중요하니 정당성 증명을 한 번 해보자.

어떤 숫자 x에 대해서 w-x에 가장 가까운 다른 숫자를 y라고 하자. 위 알고리즘이 아니라 다른 방법으로 구한 최솟값이 있다고 가정하면, y대신 다른 y' <= y인 y'과 x가 서로 그룹짓게 된다. 여기서 두 가지 경우가 있을 수 있는데,

1. y는 혼자 그룹인 경우

2. y와 다른 z가 서로 그룹을 짓는 경우

1번의 경우 (x,y'), (y)를 (x,y), (y')으로 바꿔도 답에는 변화가 없다.

2번의 경우, (x,y'), (y,z)에서, y' <= y이기 때문에 항상 (x,y), (y',z)로 서로 쌍을 바꿀 수 있다. 이 경우 답에는 변화가 없다. 같은 방법을 반복해서 위의 주어진 알고리즘으로 구한 답과 동일한 형태로 만들 수 있다.

따라서, 어느 경우든 항상 이 방법으로 구한 답이 최솟값임을 알 수 있다.