[백준 13480] Hard Cuts

티어: 루4

 

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

 

충격과 공포의 반례

 

처음에는 그리디로 풀려고 시도했었다. w와 h중 작은 값을 한 변으로 하는 정사각형을 채우고, 나머지 부분을 재귀로 다시 풀면 항상 최적의 해가 구해지는줄 알았다. 그러나 문제점이 많았다.

 

당장 눈에 보이는 반례 하나는 (w,h) = (6,5) 일때 자르는 정사각형의 최소 갯수 k가 6이 아니라 5라는것이다. 그리디하게 풀면 각 정사각형의 한 변의 길이가 5, 1, 1, 1, 1, 1 인 6개의 정사각형으로 풀리지만, 정사각형의 한 변의 길이가 3, 3, 2, 2, 2 일때의 반례가 존재한것이다.

이렇게 (w,h)에 대해 그리디하지 않은 반례가 존재하면, 자명하게도 (n*w, n*h)도 동일한 모양의 반례가 존재한다. 그래서 이 부분만 예외처리로 해결했었다.

 

하지만, 반례는 이것에서 끝나지 않았다. 정말 기상천외한 반례들이 많았는데, 아래는 삽질하며 찾은 몇가지 반례들이다.

(6,5) 3,3,2,2,2

(8,7) 4,4,3,3,2,1,1

(10,9) 5,5,4,4,1,1,1,1

(13,11) 7,6,5,4,4,1 (위 사진의 경우인데, 진짜 이건 기가막히다)

(28,25) 14,14,11,11,6,3,3,2,2,2

 

저러한 수많은 반례들에 대해 예외처리 해주고 나면, 드디어 우리가 바라던대로 풀 수 있게 된다. 나는 wwlmeel님의 블로그를 보고 백트래킹으로도 풀어서 교차 검증한 뒤, 3600가지 경우의 수에 대한 답을 전처리로 구해 제출하여 시간초과를 피했다. (그리디, 많조분 태그를 달진 않았다. 문제의 테케가 모든 반례를 포함하고 있는지도 모르겠고, 하나의 반례라도 놓친다면 wa를 받기 때문이다.)

 

 

upd: 기존에 또 다른 풀이로 적어놓았던 그리디 풀이가 반례가 발견되어 삭제했다. 비슷한 문제이지만 제약 조건이 더 있는 '백준 10803번 정사각형 만들기' 문제같은 경우, Guillotine cutting만 할 수 있다는 추가적인 제약을 통해 그리디하게 해결할 수 있다. 이러한 제약에서는 위에서 제시된 (13,11)과 같은 반례가 나오지 않기 때문이다.

직사각형을 정사각형으로 채우는것에 흥미가 있다면 이 사이트를 방문해보자.