백준 2590 - 색종이

이번 문제는 백준의 골드 5 문제인 색종이이다.
문제를 한 번 차근차근 읽어보자.

한 변의 길이가 1 ~ 6cm 정사각형 색종이의 수가 차례로 주어진다.
이 때 모든 색종이를 6 x 6 판에 다 놓으려면 몇 개의 판이 필요할까?
최소로 사용될 수 있는 판의 개수를 구해달라고 한다.
풀이가 당장 떠오르는 문제는 아닌 것 같다.

일단 가장 큰 6 x 6 색종이부터 작은 색종이 순서로 채우고,
가장 왼쪽 위의 모서리부터 채워나가면 최소의 판을 사용할 수 있을 것 같다.
그럼 관건은 색종이를 채울 공간이 있는 지 체크하는 것이라 생각한다.
어떻게 해야 해당 크기의 색종이를 채울 수 있는 지 검사할 수 있을까?

모든 경우를 다 나누어보기

가장 처음 든 생각은, 모든 경우를 다 분기시키는 것이다.
6 x 6 색종이를 넣을 때, 5 x 5 색종이를 넣을 때…
쭉 모든 색종이 별로 로직을 다 분기시킨다.
이런 생각이 든 이유는 색종이의 크기마다 할 일이 정해져 있기 때문이다.

  • 먼저, 6 x 6 색종이는 그냥 판을 다 채우게 된다.
  • 5 x 5 색종이는, 1 x 1 색종이를 추가로 받을 수 있다.
    • 11개의 1 x 1 색종이가 들어갈 수 있다.
    • 단, 1 x 1의 색종이 밖에 추가로 들어갈 수 없다.
  • 4 x 4 색종이는, 2 x 2 색종이를 추가로 받을 수 있다.
    • 5개의 2 x 2 색종이가 들어갈 수 있다.
    • 단, 1 x 1 색종이가 남으면 빈 칸에 채울 수가 있다.
  • 3 x 3 색종이는 자신 4개로 판을 모두 채울 수 있다.
    • 단 더 작은 크기의 색종이가 남으면, 추가로 채울 수 있다.
  • 만약 이후로 더 작은 크기의 색종이가 남으면 판을 마저 채운다.

내가 생각한 것은 일단 위의 로직이었다.
모든 경우를 분기시키려 했지만, 종이가 작을 수록 굉장히 분기가 많아졌다.
특히 3 x 3 종이의 경우 부터는 굉장히 머리가 아팠다.
3 x 3 종이를 쓰는 수에 따라 경우가 다시 갈라지게 된다.

이리저리 수 많은 분기를 시킨 결과 아래와 같이 구현되었다.

int color_paper[7], board[6][6], answer = 0;
void fill_space(int row) {
    switch (row)
    {
    case 6:
        answer += color_paper[row];
        break;
    case 5:
        while (color_paper[5]) {
            int leftover = 36 - 25;
            color_paper[5] -= 1;
            color_paper[1] = max(color_paper[1] - leftover, 0);
         // 남는 칸 한 칸 한 칸을 모두 1 x 1로 채울 수 있음
            answer++;
        }
        break;
    case 4:
        while (color_paper[4]) {
            int leftover = 36 - 16;
            leftover -= min(color_paper[2], 5) * 4;
        // 남는 공간은 기본적으로 2 x 2를 5개 넣을 수 있음
            color_paper[4]--;
            color_paper[2] = max(color_paper[2] - 5, 0);
        // 5개 모두 사용하거나, 더 많이 쓰는 경우엔 0으로 만듬
            color_paper[1] = max(color_paper[1] - leftover, 0);
        // 완전 나머지 공간은 1로 다 채울 수 있음
            answer++;
        }
        break;
    case 3:
        while (color_paper[3]) {
            int leftover = 36 - (9 * min(color_paper[3], 4));

            // 3x3은 1~4개 쓸 때 모두 해야할 일이 다르다.
            if (color_paper[3] >= 4)
                color_paper[3] -= 4;
            else if (color_paper[3] == 3) {
                leftover -= min(color_paper[2], 1) * 4;
                color_paper[3] -= 3;
                color_paper[2] = max(color_paper[2] - 1, 0);
            // 3개를 쓸 때는 2 x 2가 1개 밖에 못들어간다.
            }
            else if (color_paper[3] == 2) {
                leftover -= min(color_paper[2], 3) * 4;
                color_paper[3] -= 2;
                color_paper[2] = max(color_paper[2] - 3, 0);
            // 2개를 쓸 때는 2 x 2가 3개 들어간다.
            }
            else {
                leftover -= min(color_paper[2], 5) * 4;
                color_paper[3] -= 1;
                color_paper[2] = max(color_paper[2] - 5, 0);
            // 1개를 쓸 때는 2 x 2가 5개 들어간다.
            }

            // 남는 공간은 1로 다 채우도록 하자
            color_paper[1] = max(color_paper[1] - leftover, 0);
            answer++;
        }
        break;
    case 2:
        while (color_paper[2]) {
            int leftover = 36 - 4 * min(color_paper[2], 9);
            // 순수하게 2 x 2로는 9칸을 채울 수 있다.
            color_paper[2] = max(color_paper[2] - 9, 0);
            color_paper[1] = max(color_paper[1] - leftover, 0);
            // 2 x 2로 최대로 채우고 남는 공간은 1로 마저 채운다.
            answer++;
        }
        break;
    case 1:
        while (color_paper[1]) {
            color_paper[1] = max(color_paper[1] - 36, 0);
            answer++;
        }
        break;
    }
}

굳이 문제를 분류하자면 그리디 알고리즘 문제였다고 한다.
나는 사실상 구현에 가까운 문제라고 생각한다.