블록 쌓기

직육면체 모양의 나무 블록의 크기는 (L(길이), W(너비), H(높이))로 결정된다. 주어진 블록을 가능한 높이 쌓으려고 한다. 단, 안정성을 고려해서 아래에 놓이는 블록의 길이과 너비는 위에 놓인 블록의 길이와 너비보다 각각 같거나 커야 한다. 모든 블록은 회전이 가능하다.

예를 들어, 아래 그림 좌측에서 보인 것처럼 두 블록의 크기가 각각 (3,5,3)과 (3,4,5)일 때, 그림 우측에 보인 것처럼 쌓으면 높이가 10이 되고, 이는 가장 높게 쌓은 모양이다.

주어진 3개의 블록 크기가 각각 (2,5,8), (4,4,9), (3,2,4)일 때, 이들을 가능한 높게 쌓는다면 그 높이는 얼마가 되는가?

문제 형식

주관식

출처

• KOI 2022 1차대회 고등부 1교시 3번
• KOI 2022 1차대회 초등부 1교시 11번