[백준] 고기잡이

https://www.acmicpc.net/problem/7573

7573번: 고기잡이

문제부터 간단하게 요약하면, 

그물의 크기가 주어질 때, 가장 많은 물고기를 잡을 수 있는 경우, 몇 마리를 잡을 수 있는지를 구해야 하는 문제입니다.

 

<Solution>

일단 그물의 종류별로 확인을 해야 하는 것은 당연합니다.

예를 들면 길이 10인 그물이 주어진다면, 1x4, 2x3, 3x2, 4x1 의 그물 종류에 대해 모두 확인해야 하는 것은 당연합니다. 

 

하지만 모든 점에 대해 이 그물 종류들을 모두 조사하게 된다면, 시간 초과가 나게 됩니다. 

(시간초과 코드 예시)

#include <iostream>
 
using namespace std;
 
int N, L, M;
char grid[10000+10][10000+10];
 
int sol(){
    L = L+4; 
    // if ( L >= 4*(N-1)) L = 4*(N-1);
    int new_L = (L)/2;
    int ans = 0;
    for(int H = 2; H<new_L-1; H++){
        int W = new_L-H;
        // r c bound
 
        for(int i = 1; i<= N+1-(H); i++){
            for(int j = 1; j<=N+1-(W); j++){ // cnt
                int tmp = 0;
                for(int r = i; r<i+H; r++){
                    for(int c = j; c<j+W; c++){
                        if(grid[r][c] == '1') tmp++;
                    }
                }
                ans = max(ans, tmp);
            }
        }
 
    }
    return ans;
 
 
}
 
 
 
int main(){
    cin >> N >> L >> M;
    int r,c;
    for(int i = 0; i<M; i++){
        cin >> r >> c;
        grid[r][c] = '1';
    }
 
    // done with input
    int ans = sol();
    cout << ans << endl;
    return 0;
 
}

 

따라서 좀더 나은 방법을 생각해야 합니다. 

 

잘 생각해보면, 만약 물고기가 그물에 걸리면서 다른 물고기를 최대한 많이 포함하려면, 해당하는 물고기가 그물의 끝에 걸려야 하는 것을 생각 할 수 있습니다. 

그물의 경우 그물의 1x4, 4x1 가로, 세로가 바뀌는 상황들에 대해 모두 탐색할 것이므로, 우리는 각각의 물고기가 그물의 한쪽 끝에 걸리는 상황들에 대해서만 모두 탐색을 하면 되는 것을 알 수 있습니다. 

 

그림으로 예시를 들면, 

다음 처럼 2x3의 그물이 쳐지는 상황에 (3,3)의 물고기에 대한 탐색을 한다고 치면, 분홍색으로 표시된 3개의 그물만 탐색하면 되는 것을 알 수 있습니다.

 

따라서 로직을 세워보면 

1. 각각의 물고기에 대해  2. 각각의 그물 종류에 대해 3. 물고기가 왼쪽 끝에 걸리는 경우에 대해서 탐색한다.

위와 같은 로직이 세워지고 

실제 구현은 아래와 같습니다.

#include <iostream>

using namespace std;

int N, L, M;
char grid[10000+10][10000+10];
struct fish{
    int r, c;
};

struct fish fish_array[120];

int sol(){
    L = L+4; 
    int new_L = (L)/2;
    int ans = 0;
    for(int H = 2; H<new_L-1; H++){
        int W = new_L-H;
        // r c bound
        // 그물 사이즈 제작완료
        for(int i = 0; i<M; i++){
            int fish_r = fish_array[i].r;
            int fish_c = fish_array[i].c;

            // find search range
            // column range

            int new_row_min = fish_r - (H-1);
            int new_row_max = fish_r;
            if(new_row_min < 1) new_row_min = 1;
            
            for(int p = new_row_min ; p<= new_row_max; p++){
                int tmp = 0;
                for(int r = p; r<p+H; r++){
                    for(int c = fish_c; c<fish_c+W; c++){
                        if(grid[r][c] == '1') tmp++;
                    }
                }
                    ans = max(ans, tmp);
            }
        }

    }
    return ans;

}



int main(){
    cin >> N >> L >> M;
    int r,c;
    for(int i = 0; i<M; i++){
        cin >> r >> c;
        grid[r][c] = '1';
        fish_array[i].r = r;
        fish_array[i].c = c;
    }

    // done with input
    int ans = sol();
    cout << ans << endl;
    return 0;

}