POJ. - 1017 욕심.

4231 단어 탐욕스럽다
이 문제는 어렵지 않다. 관건은 사고방식을 필터하고 어떻게 놓는 것이 가장 큰 이용 공간인지 명확하게 하는 것이다.
그리고 POJ는 왜 그런지 몰라서 며칠 동안 터졌는데 이 문제를 오랜만에 제출했다.
아이디어:
6*6:하나에 상자 하나 독점
5*5:하나는 하나의 상자를 독점해야 하며, 다 넣으면 11개를 더 넣을 수 있다.
4*4: 하나는 하나의 상자를 독점해야 하며, 다 넣은 후에 5개의 2*2(먼저 큰 것을 꽉 끼게 놓고)를 넣을 수 있다. 그리고 여유가 있으면 1*1로 채울 수 있다.
3*3: 이건 좀 귀찮아요. 상황을 분리해서 생각해야 해요.
2*2와 1*1은 위의 사고방식과 같다.
 
코드가 간결하지 않으니 다들 아쉬운 대로 보세요. 어쨌든 ac입니다.
#include 

using namespace std;

int a[7];

int main()
{
    while (!cin.eof())
    {
        int sum = 0;
        for (int i = 1; i <= 6; i++) {cin >> a[i]; sum += a[i];}

        if (!sum) break;

        int ans = 0;
        if (a[6]) ans += a[6];
        if (a[5])
        {
            ans += a[5];

            int area = a[5] * 11;

            a[1] = (a[1] - area) <= 0 ? 0 : (a[1] - area);
        }
        if (a[4])
        {
            ans += a[4];
            int area = 20 * a[4];
            if (a[2])
            {
                if (area - a[2] * 4 <= 0)
                {
                    a[2] -= (area / 4);
                    area = 0;
                }
                else
                {
                    area -= a[2] * 4;
                    a[2] = 0;
                }

            }

            if (area && a[1])
            {
                if (area - a[1] <= 0) a[1] -= area;
                else a[1] = 0;
            }
        }

        if (a[3])
        {
            ans += (a[3] / 4);
            a[3] %= 4;        //3*3      
            if (a[3]) {
                int area = 36 - (9 * a[3]);
                ans += 1;

                if (a[3] == 1)
                {
                    area = 27;
                    if (a[2])
                    {
                        if (a[2] <= 5)
                        {
                            area -= (4 * a[2]);
                            a[2] = 0;
                        }
                        else
                        {
                            area -= 20;
                            a[2] -= 5;
                        }
                    }

                    if (area)
                    {
                        if (a[1])
                        {
                            if (a[1] <= area) a[1] = 0;
                            else a[1] -= area;
                        }
                    }
                }
                else if (a[3] == 2)
                {
                    area = 18;
                    if (a[2])
                    {
                        if (a[2] <= 3)
                        {
                            area -= (4 * a[2]);
                            a[2] = 0;
                        }
                        else
                        {
                            area -= 12;
                            a[2] -= 3;
                        }
                    }

                    if (area)
                    {
                        if (a[1] >= area) a[1] -= area;
                        else a[1] = 0;
                    }

                }
                else if (a[3] == 3)
                {
                    if (a[2])
                    {
                        a[2] -= 1;

                        if (a[1])
                        {
                            if (a[1] <= 5) a[1] = 0;
                            else a[1] -= 5;
                        }
                    }
                    else
                    {
                        if (a[1])
                        {
                            if (a[1] <= 9) a[1] = 0;
                            else a[1] -= 9;
                        }
                    }

                }
            }
        }


        if (a[2])
        {
            ans += (a[2] / 9);
            a[2] %= 9;


            if (a[2])
            {
                int area = 36 - (4 * a[2]);

                a[1] = (a[1] - area <= 0) ? 0 : (a[1] - area);

                ans++;

            }
        }

        if (a[1])
        {
            ans += (a[1] % 36 == 0) ? (a[1] / 36) : (a[1] / 36) + 1;
        }

        cout << ans << endl;

    }
    return 0;
}

좋은 웹페이지 즐겨찾기