BOJ 2590 색종이(C++)

색종이 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	128 MB	429	151	119	42.652%

문제

<그림 1>과 같이 정사각형 모양을 한 여섯 종류의 색종이가 있다. ①번 색종이는 한 변의 길이가 1cm이고, 차례대로 그 길이가 1cm씩 커져, ⑥번 색종이의 한 변의 길이는 6cm가 된다.

주어진 색종이를 <그림 2>와 같이 가로, 세로의 길이가 각각 6cm인 판 위에 붙이려고 한다. 색종이를 붙일 때는 색종이가 판의 경계 밖으로 삐져 나가서는 안되며, 색종이가 서로 겹쳐서도 안된다. 또한 하나의 색종이는 하나의 판에만 붙여야 한다.

각 종류별로 색종이의 장수가 주어질 때, 그 색종이를 모두 붙이기 위해서 위와 같은 판이 최소 몇 개가 필요한지 구하는 프로그램을 작성하시오.

입력

첫째 줄부터 여섯째 줄까지 각 종류의 색종이의 장수가 ①번부터 ⑥번까지 차례로 주어진다. 각 종류의 색종이의 장수는 최대 100이다.

출력

첫째 줄에 필요한 판의 최소 개수를 출력한다.

예제 입력 

5
3
0
1
1
0

예제 출력 

2

힌트

출처

Olympiad > 한국정보올림피아드시․도지역본선 > 지역본선 2005 > 초등부 4번

Olympiad > 한국정보올림피아드시․도지역본선 > 지역본선 2005 > 중등부 2번

#include    <cstdio>
#pragma warning(disable : 4996)
 
int P[10];
int main()
{
    int res = 0;
    for (int i = 1; i <= 6; ++i)
    {
        scanf("%d", &P[i]);
    }
 
    // 6인 색종이는 무조건 1:1 대칭
    res = P[6];
 
    // 5인 색종이는 무조건 1개당 1이 6x6 36 5x5 25 1이 11개 들어갈 수 있음. 
    int five = P[5];
    P[1] -= five * 11;
    if (P[1] < 0)
        P[1] = 0;
    res += five;
 
    //4인 색종이는 6x6 36 4x4 16 20 4 4 4 4 4 2x2 5개 들어갈 수 있음. 
    int four = P[4];
    int cap2by2 = four * 5; //남은 공간. 2x2기준으로
    if (cap2by2 < P[2])
        P[2] -= cap2by2;
    else
    {
        cap2by2 -= P[2];
        P[2] = 0;
 
        //남은 공간은 1로 채워줌.
        int cap1by1 = cap2by2 * 4;
        P[1] -= cap1by1;
        if (P[1] < 0)
            P[1] = 0;
    }
    res += four;
    //3인 색종이는 3x3 9 6x6 36
    int three = P[3] / 4;
    if (P[3] % 4 != 0) //3x3이 1~3개가 남으면
        three++;
 
    //남은 공간에 2를 채워줌.
    //3x3 = 1
    if (P[3] % 4 == 1)
    {
        //남은 공간 - 2를 채울 수 있는 공간 5개 채울 수 있음.
        int cap2by2 = 5;
 
        if (P[2] > cap2by2)
        {
            P[2] -= cap2by2;
            int cap1by1 = 9; //가능한 공간
            P[1] -= cap1by1;
            if (P[1] < 0)
                P[1] = 0;
        }
        else
        {
            cap2by2 -= P[2];
            P[2] = 0;
            int cap1by1 = 9 + cap2by2 * 4;
            P[1] -= cap1by1;
            if (P[1] < 0)
                P[1] = 0;
        }
    }
    //3x3 = 2
    else if (P[3] % 4 == 2)
    {
        int cap2by2 = 3;
        if (P[2] > cap2by2)
        {
            P[2] -= cap2by2;
            int cap1by1 = 6; //가능한 공간
            P[1] -= cap1by1;
            if (P[1] < 0)
                P[1] = 0;
        }
        else
        {
            cap2by2 -= P[2];
            P[2] = 0;
            int cap1by1 = 6 + cap2by2 * 4;
            P[1] -= cap1by1;
            if (P[1] < 0)
                P[1] = 0;
        }
    }
    //3x3 = 3
    else if (P[3] % 4 == 3)
    {
        int cap2by2 = 1;
        if (P[2] > cap2by2)
        {
            P[2] -= cap2by2;
            int cap1by1 = 5; //가능한 공간
            P[1] -= cap1by1;
            if (P[1] < 0)
                P[1] = 0;
        }
        else
        {
            cap2by2 -= P[2];
            P[2] = 0;
            int cap1by1 = 5 + cap2by2 * 4;
            P[1] -= cap1by1;
            if (P[1] < 0)
                P[1] = 0;
        }
    }
    res += three;
    //2x2 
    int two = P[2] / 9;
    if (P[2] % 9 != 0)
    {
        two++;
        int cap1by1 = 36 - 4 * (P[2] % 9);
        P[1] -= cap1by1;
        if (P[1] < 0)
            P[1] = 0;
 
    }   
    res += two;
    //1x1
    int one = P[1] / 36;
    if (P[1] % 36 != 0)
        one++;
    res += one;
 
    printf("%d\n", res);
    return 0;
}

음.. 이건 좀 이렇게 푸는게 맞나 싶을 정도로 길고 if문의 연속이었다. 

가장 중요한 포인트는 색종이 하나는 무조건 한 판 안에 들어가야 한다. 두 판에 겹쳐서 놓을수는 없다는 것인데

이걸 못봐서 일주일을 고민했다... 어떻게 풀어야할까... 하다가 이걸 보니 그냥 if문으로도 풀 수 있겠다 싶어서

마구잡이로 코딩을 했다.. 우선 맞기는 했는데 다른방법이 있지 않을까 싶다. 

푼 방법은 

6인 색종이는 무조건 한판에 하나 들어가므로 판의 장수와 동일 

5인 색종이도 한판당 하나 들어가므로 판의 장수와 동일하나 1인 색종이를 넣을 수 있다. (최대 11개) 

4인 색종이도 한판당 하나 들어가므로 판의 장수와 동일하나 2인 색종이, 1인 색종이를 넣을 수 있다. 

3인 색종이는 한판당 4개까지 들어가고 남은 공간에는 2인 색종이, 1인 색종이를 넣을 수 있다.

2인 색종이는 한판당 9개까지 들어가고 남은 공간에는 1인 색종이를 넣을 수 있다. 

1인 색종이는 한판당 36개까지 들어간다. 

이것을 그대로 코드화 하였다.