Problem Statement
큐브더미가 쌓여있습니다. 중력때문에 큐브는 항상 아래쪽부터 채워져 있습니다. (공중에 떠 있지 않습니다.)
이 큐브더미의 상면도, 정면도, 측면도가 주어져 있습니다. 이 그림들을 가지고 최대 몇 개의 큐브를 사용했는지 유추하는 문제입니다. 만약 현실적으로 불가능한 경우라면 -1을 출력합니다.
Analysis
대회때 O(n^3)으로 해도 답이 나왔다고 들었는데.. 확실치는 않습니다. 참가자가 아니니까요..;;
여기서는 O(n^2) 알고리즘으로 설명하도록 하겠습니다. n^2으로 접근할 수 있는 이유는 '중력에 의해 큐브는 아래쪽부터 차 있다'는 조건 때문이지요.
정면도와 측면도를 이용하면 어떤 지점에서의 최대 높이를 구할 수 있습니다. 그리고 상면도에서 봤을 때, 0이 아니라면 그 높이만큼의 큐브를 쌓아도 모순이 생기지 않는다는 뜻이지요. 이를 이용하여 모든 지점에 큐브를 쌓아둡니다.
그리고 모순이 있는지 체크를 하기 위해 실제로 쌓아둔 큐브를 가지고 같은 정면도/측면도가 나오는지 체크합니다. (상면도는 위에서 큐브를 쌓는다/쌓지 않는다에서 체크하기 때문에 다시 볼 필요는 없지요.)
astein
16년 전