[SWEA] 2001. 파리 퇴치 (D2) / C++

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PzOCKAigDFAUq

SW Expert Academy

---

그냥 for문으로 쭉~ 돌아도 되려나..? 싶었지만

 

1) 들어오는 값으로 파리의 평균 값을 구하고

2) 해당 평균값보다 높은 좌표를 우선 돌아보도록 했다.

이런식으로, *칸의 파리수가 많아서 확인하고 싶다면,

M*M파리채가 해당 사이즈만큼 돌면서 체크하는 방식이다.

 

처음에 든 아이디어가 이거였는데 막상 구현을 해보니 좀 효율적이진 않은 듯..ㅎㅎ

아래는 코드임

 

#include<iostream>
#include<vector>
using namespace std;
 
int N, M;
int result = -1;
float Average = 0;
int** flies;
 
int SumOfFlies(int x, int y)
{
    int sum = 0;
    for (int i = x; i < x + M; i++)
    {
        for (int j = y; j < y + M; j++)
        {
            if (i < 0 || i >= N || j < 0 || j >= N) continue;
            sum += flies[i][j];
        }
    }
 
    return sum;
}
 
 
int main(int argc, char** argv)
{
    int test_case;
    int T;
    cin >> T;
 
    for (test_case = 1; test_case <= T; ++test_case)
    {
        cin >> N >> M; // N*N의 격자, M*M의 파리채
 
        // 2차원 Array 동적할당
        flies = new int*[N];
        for (int i = 0; i < N; i++)
            flies[i] = new int[N];
 
        int temp;
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                cin >> temp;
                Average += temp;
                flies[i][j] = temp;
            }
        }
 
        Average = Average / ((float)N * N);
 
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
            {
                // 해당 격자의 파리 수가 평균보다 높다면, 검사한다.
                if (flies[i][j] > Average)
                {
                    for (int dx = i - (M - 1); dx <= i ; dx++)
                        for (int dy = j - (M - 1); dy <= j; dy++)
                        {
                            if (dx < 0 || dx >= N || dy < 0 || dy >= N)
                                continue;
 
                            // cout << "dx: " << dx << ", dy: " << dy << "\n";
                            int resultSum = SumOfFlies(dx, dy);
                            if (resultSum > result)
                                result = resultSum;
 
                        }
                }
            }
 
        cout << "#" << test_case << " " << result << "\n";
 
        //메모리 해제
        for (int i = 0; i < N; i++) 
        {
            free(flies[i]);
        }
        free(flies);        
        Average = 0;
        result = -1;
    }
    return 0;//정상종료시 반드시 0을 리턴해야합니다.
}

 

 

작성한 코드를 보면 for문이 무지하게 많지만..

그래도 처음부터 다~ 도는 것 보다는 낫지 싶다. 아니 다 돌아도 시간 초과 안 나나?

 

댓글에 보니 누적합 알고리즘으로 풀 수 있다고 하던데.. 공부해봐야겠다!

https://velog.io/@dnflrhkddyd/SWEA-2001.-%ED%8C%8C%EB%A6%AC-%ED%87%B4%EC%B9%98

[SWEA] 2001. 파리 퇴치