[C++] SWEA 1251번: 단순도금비용

🔗 문제

SW Expert Academy

SW Expert Academy

[S/W 문제해결 응용] 5일차 - 단순도금비용

 

🖍 풀이

 

🚩 주의: 단순도금비용은 Pass지만, 도금 비용은 Fail이에요.

 

문제를 보면 가장 큰 필름부터 붙이는 것이 좋겠다는 생각이 든다.

 

 

1) 먼저 손상 개수별로 최소 비용으로 수리할 수 있는 필름 크기를 알아보자.

• 9~5개는 사이즈가 3인 필름을 붙이는 것이 최소 비용
• 4~2개는 사이즈가 2인 필름을 붙이는 것이 최소 비용
• 1개는 사이즈가가 1인 필름을 붙이는 것이 최소 비용

이를 토대로 손상 개수 범위를 지정했다.

const int size_range[3][2] = {{1, 1}, {4, 2}, {9, 5}};

 

 

2) 맵을 돌면서 (x, y)위치에서 size 범위 내에 손상 개수를 세어주고 손상 개수가 가장 큰 것부터 붙여줬다.

 

 

사이즈 3으로 해결할 수 있다고 먼저 수리해버리면 안되는 이유 예시 첨부

→ 범위 내에 손상 개수가 큰 것인 것부터 일단 수리하는 게 이득이다!

 

만약 (x, y)를 순서대로 돌다가 아래 파란 박스를 먼저 수리한다면??… 최소 비용이 아니다!!

 

이렇게 꽉꽉 더 많은 손상 개수를 붙인 다음에 나머지를 더 작은 사이즈로 수리하는 것이 더 싸다.

 

[BOJ 색종이 붙이기]를 풀었던 기억이 있어서 완전 탐색으로 풀어줬다.

색종이 붙이기와 다르게 이 문제는 “모든 위치”에서 탐색이 필요하다.

파란 체크 부분에서 탐색을 하지 않았더라면 정답을 놓치는 것을 확인할 수 있다.

 

(x, y)가 손상됐든 말든 정말 완전 탐색해준다.

 

+ 인덱스 시작이 1이므로 map을 돌 때 1부터 돌아주었다. (조금이라도 시간을 아끼려고..)

 

💾  소스

#include <iostream>
#include <memory.h>
#define MAX 10000 + 5

const int size_range[3][2] = {{1, 1}, {4, 2}, {9, 5}};

int T, N;
int answer_cnt;
int answer_x[MAX] = {0, };
int answer_y[MAX] = {0, };
int answer_size[MAX]  {0, };
bool map[105][105] = {false, };

// 수리 표시
void setter(const int x, const int y, const int size, const bool b)
{
    for(int i=x; i<x+size; ++i)
    {
        for(int j=y; j<y+size; ++j)
        {
            map[i][j] = b;
        }
    }
}

// x, y위치에서 size범위 내의 손상 개수를 반환한다. 
int counter(const int x, const int y, const int size)
{
    int result = 0;
    for(int i=x; i<x+size; ++i)
    {
        for(int j=y; j<y+size; ++j)
        {
            if(map[i][j])
            {
                result++;
            }
        }
    }
    return result;
}

void solve()
{
    for(int size=2; size>=0; --size)
    {
        for(int cnt = size_range[size][0]; cnt>= size_range[size][1]; --cnt)
        {
            // 완전 탐색
            for(int x=1; x<=N; ++x)
            {
                for(int y=1; y<=N; ++y)
                {
                    //같은 사이즈 필름이라도 손상 개수 많이 덮을 수 있도록 하기 위해서 cnt 반복문 씀
                    if(counter(x, y, size+1) == cnt)
                    {
                        answer_x[answer_cnt] = x;
                        answer_y[answer_cnt] = y;
                        answer_size[answer_cnt] = size+1;
                        answer_cnt++;
                        setter(x, y, size+1, false);
                    }
                }
            }
        }
    }
}

int main()
{

    int M, x, y;
    std::cin >> T;
    for(int tc=1; tc<=T; ++tc)
    {
        //init
        answer_cnt = 0;
        memset(map, false, sizeof(map));

        
        //input
        std::cin >> N >> M;
        for(int i=0; i<M; ++i)
        {
            std::cin  >> x >> y;
            map[x][y] = true;
        }
        
        
        solve();
        
        
        //output
        std::cout << '#' << tc << ' ' << answer_cnt << ' ';
        for(int i=0; i<answer_cnt; ++i)
        {
            std::cout << answer_x[i] << ' ' << answer_y[i] << ' ' << answer_size[i] <<' ';
        }
        std::cout << '\\n';
        
    }
    return 0;
}