[코딩 테스트 RUN] SWEA 수업 : 2001. 파리퇴치

 

⚠️ 주의!
SWEA에서 낸 코딩 문제에 대한 해답이 들어있습니다.
열람 시 주의해주세요.

 

풀면서 내내 응? 하고 의심하던 문제. 그것이 정답이었을 때 너무 당황스러웠는데, 다행히도 더 괜찮은 답이 있었다(이건 AI가 대답해주어서 알게 되었다).

 

[SW Expert Academy] 2001. 파리퇴치

SW Expert Academy

 

일단 여기에서 파리들의 배열을 만든다. 이것까진 문제가 없다.

중요한 건 파리채의 범위인데, 파리채의 범위를 0부터 시작한다고 할때 그대로 끝까지 파리들의 범위를 하면 안된다. 파리의 범위 N에서 파리채의 범위 M을 빼야하는데, 여기서 평소대로 미만처리하지 말고 이하로 넣을 것(이 부분이 포인트이다.). 왜냐하면 N-M 자체가 마지막 칸이기 때문이다(경계가 딱 맞닿는 부분이다.)

 

그리고 이중 배열을 더 추가한다. 파리채의 범위의 0에서부터 순서대로 시작하여 더해야 하기 때문이다.

 

내가 제출한 정답

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Solution {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        for(int test_case = 1; test_case <= T; test_case++) {
            //테스트 케이스 입력
            StringTokenizer st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());

            //array 길이 설정
            int[][] fly = new int[N][N];

            for(int i = 0; i < N; i++){
                StringTokenizer stNum = new StringTokenizer(br.readLine());
                for (int j = 0; j < N; j++) {
                    fly[i][j] = Integer.parseInt(stNum.nextToken());
                }
            }

            int max = 0;
            for (int x = 0; x <= N - M; x++) {
                // 시작 행
                for (int y = 0; y <= N - M; y++) {
                    //시작 열
                    int sum = 0;
                    for (int j = 0; j < M; j++) {
                        for (int k = 0; k < M; k++) {
                            sum += fly[x + j][y + k];
                        }
                    }
                    max = Math.max(sum, max);
                }
            }
            System.out.printf("#%d %d%n", test_case, max);
        }

    }
}

 

AI의 답변

// 1. 누적 합 배열 만들기 (인덱스 편의상 N+1 크기 사용)
int[][] acc = new int[N + 1][N + 1];

for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= N; j++) {
        // 현재값 + 위쪽 + 왼쪽 - 중복된 대각선
        acc[i][j] = fly[i-1][j-1] + acc[i-1][j] + acc[i][j-1] - acc[i-1][j-1];
    }
}

int max = 0;

// 2. 파리 잡기 (2중 for문)
for (int i = M; i <= N; i++) {
    for (int j = M; j <= N; j++) {
        // (i, j)를 우측 하단으로 하는 MxM 사각형 합 구하기
        // 전체 - 위쪽부분 - 왼쪽부분 + 중복해서 뺀 대각선부분
        int sum = acc[i][j] - acc[i-M][j] - acc[i][j-M] + acc[i-M][j-M];
        max = Math.max(max, sum);
    }
}

 

이건 바로 누적 합 형태로, 누적합의 배열을 만드는 것이다. 배열을 추가 생성하기 때문에 메모리가 들긴 하지만, 크기 때문에 크게 중요하진 않다. 사실 누적합 관련해서는 풍선팡 보너스 게임에서 해본 적이 있는데, 이건 4중인걸 생각하면 비슷한 문제라고 생각해도 거의 무방한 수준.

보다시피 '누적합' 배열을 만들고, 점진적으로 현재값 + 위쪽 + 왼쪽을 넣는다. 그리고 중복된 값은 제외한다.

 

그리고 파리 잡기를 시작하는데, 위에서한 j와 k의 2중 for문이 여기서 시작된다고 볼 수 있다. 여기서 미리 넣어둔 배열의 합을 참고하여, -M만큼의 값을(우측 하단으로 하므로) 하여 M*M의 누적합 값을 만든다. 전체 - 위쪽 - 왼쪽 + 중복해 뺀 대각선 부분이다.

 

뭔소린가 싶을 텐데, 이미지로 나타내면 이러하다.

 

 

이게 지금 N x N 배열의 파리이다. i가 행, j가 열이다.

여기서 이 누적합에서는 0이 아니라 1부터 시작했다(왜냐하면 -1을 다루기 때문이다)

 

acc[1][1]은

 

 

여기를 나타낸다. 왜냐하면 acc[0][0]은 없고, 1부터 시작하기 때문이다(즉 편의상 경계 바깥을 따진다고 볼 수 있다.)

여기서 acc[1][2]가 된다고 치자. 그렇다면

이게 acc[1][2]의 값이 된다.

 

여기서 acc[2][1]이 된다고 친다면,

 

여기까지가 합이 된다. 그러므로 만약에 저기 있는 13, 즉 [2][2]가 된다면,

 

이렇게 겹쳐서 합산이 되므로, 1은 한번 빼줘야 하는 것이다. 따라서 25가 acc[2][2]의 누적합이 된다.

그래서 아래의 경우에는 M에서부터 시작한다. M이 2x2라고 한다면, [2][2]에서 시작한다.

acc의 [2][2]는 25이고, 여기서 [2][0], [0][2], [0][0]이다. 0은 경계선 밖이므로 당연히 0값. 따라서 acc[2][2]는 25가 된다.

 

이렇게 누적합이 되다보면 자신으로부터 위쪽과 왼쪽에 있는 것이 합산에 포함되기 때문에, 그것들을 빼주고 중복으로 뺀걸 추가한 것이다.

이렇게하면 비교적 쉽게 구할 수 있다.