[백준/C++] 조용히 하라고!!

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제를 처음 봤을 때, 완전 탐색을 해야겠다는 생각이 들었다.

왜냐하면 모기를 가장 많이 잡는 루트를 탐색하는 최적의 방법이 없다고 판단했기 때문이다.

 

시간 복잡도는 O(N*M*K+K!) 으로 N과 M이 충분히 작고 K도 10으로 매우 작아 계산해보면 충분히 완전 탐색을 해도 통과할 것이라고 생각했다. (10! = 3,628,800)

 

우정이는 모기를 잡는 순서를 따라 이동하면서 이동시간을 초과하지 않을 때 까지 모기를 잡는다.

그렇게 모든 경우를 계산해 가장 모기를 많이 잡은 경우를 저장한다.

(우정이는 모기가 있는 위치에서 시작하는게 무조건 유리하다.)

 

아름이는 N*M범위에 모기장을 전부 설치해 비교해야한다.

(모기가 있는 위치가 아닌 곳에 모기장을 설치하는게 유리할 수 있기 때문)

이후 N*M 범위에 모기장을 설치해 K개의 모기 중 몇 마리의 죽는지 비교해 최대값을 저장하면 된다.

 

 

 

​

[아이디어 정리]

1. 우정이는 모기를 잡는 순서를 고려해 모든 경우를 계산하고, 모기를 가장 많이 잡는 경우를 저장한다. (이 때,  체력이 남는 동안에만 탐색)
2. 아름이는 N*M범위에 모기장을 설치하는 경우를 전부 비교하고 그 중 가장 모기를 많이 잡는 경우를 저장한다.
3. 위에서 구한 두 경우를 출력한다.

 

 

 

Code

 

 

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int pKill = 0;
int pFlag = false;
bool DFS(int killK, int K, int nowH, vector<bool>& isKill, int prevR, int prevC, vector<vector<int>> &mosV)
{
    pKill = max(pKill, killK);
    if (killK == K) {
        return true;
    }
    for (int i=0; i<mosV.size(); i++)
    {
        if (!isKill[i]&&nowH>=abs(prevR-mosV[i][0]) + abs(prevC - mosV[i][1]))
        {
            isKill[i] = true;
            pFlag=DFS(killK + mosV[i][2], K, nowH - (abs(prevR - mosV[i][0]) + abs(prevC - mosV[i][1])), isKill, mosV[i][0], mosV[i][1], mosV);
            if (pFlag) {
                return true;
            }
            isKill[i] = false;
        }
    }
    return false;
}


int main()
{
    int elecKill = 0;
    ios::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    int N, M, K, T, P;
    cin >> N >> M >> K >> T >> P;
    int r, c, s;
    vector<vector<int>>mosRC(K, vector<int>(3));
    vector<vector<int>> mosV;
    vector<int> temp(3, 0);
    for (int i = 0; i < K; i++) {
        cin >> r >> c >> s;
        mosRC[i][0] = r, mosRC[i][1] = c, mosRC[i][2] = s;
        bool flag = false;
        for (int j=0; j<mosV.size(); j++)
        {
            if (mosV[j][0]==r&&mosV[j][1]==c)
            {
                mosV[j][2] += 1;
                flag = true;
                break;
            }
        }
        if (!flag)
        {
            mosV.push_back(vector<int>{r, c, 1});
        }
    }
    for (int i=1; i<=N; i++)
    {
        for (int j=1; j<=M; j++)
        {
            int tempKill = 0;
            for (int k = 0; k < mosRC.size(); k++)
            {
                if (i == mosRC[k][0] && j == mosRC[k][1])
                {
                    tempKill += 1;
                }
                else 
                {
                    if (mosRC[k][2]<=P/(abs(i-mosRC[k][0])+abs(j-mosRC[k][1])))
                    {
                        tempKill += 1;
                    }
                }
            }
            elecKill = max(elecKill, tempKill);
        }
    }
    vector<bool> isKill(mosV.size(),false);
    for (int i=0; i<mosV.size(); i++)
    {
        isKill[i] = true;
        DFS(mosV[i][2], K, T, isKill, mosV[i][0], mosV[i][1], mosV);
        isKill[i] = false;
    }

    cout <<pKill<<" " << elecKill;


    return 0;
}

 

---

이 문제를 처음 봤을 때, 완전탐색을 해도 풀릴 것이라고 바로 판단하고 풀었었다.

그런데 이상하게 시간초과가 나서 못 풀었다;;

왜 안 풀리는지 이해가 안돼서 지금 코드와 비교했더니 재귀를 하는 과정에서 필요없는 복사와 생성이 많이 일어나서 시간초과가 난 것이었다... ㅠㅠㅠ