[C] SW Expert Academy 문제풀이 :: 2001번

파리 퇴치 문제. 2차원 배열을 만들어야 하는데, 2차원 포인터로 동적할당을 사용하고 싶었다. 몇 개 풀어보니깐 2단계 문제는 알고리즘 자체가 어려운 건 없다. 다만 내가 C를 아직 능숙하게 사용하지 못해서 헷갈리는 부분이 좀 있다.

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PzOCKAigDFAUq&categoryId=AV5PzOCKAigDFAUq&categoryType=CODE

N x N 배열 안의 숫자는 해당 영역에 존재하는 파리의 개수를 의미한다. M x M 크기의 파리채를 한 번 내리쳐 최대한 많은 파리를 죽이고자 한다. 죽은 파리의 개수를 구하라!

풀이

#include <stdio.h>
#include <malloc.h>
 
int killCounter(char **array, int rowStart, int colStart, int m) {
    int killNum = 0;
    
    for (int i = rowStart; i < rowStart + m; i++) {
        for (int j = colStart; j < colStart + m; j++) {
            killNum += array[i][j];
        }
    }
 
    return killNum;
}
 
int main() {
    int tc;
 
    scanf("%d", &tc);
    
    for (int t = 0; t < tc; t++) {
        int n, m, temp;
        int kill = 0;
        char **array;
 
        scanf("%d %d", &n, &m);
 
        array = (char **)malloc(sizeof(char*)*n);
 
        for (int i = 0; i < n; i++) {
            array[i] = (char*)malloc(sizeof(char)*n);
            for (int j = 0; j < n; j++) {
                scanf("%d", &array[i][j]);
            }
        }
 
        for (int i = 0; i < n - m + 1; i++) {
            for (int j = 0; j < n - m + 1; j++) {
                temp = killCounter(array, i, j, m);
                if (temp > kill) {
                    kill = temp;
                }
            }
        }
 
        printf("#%d %d\n", t+1, kill);
    }
 
    return 0;
}

표준입출력과 동적할당, <stdio.h>와 <malloc.h> 헤더를 호출한다.

배열의 x, y 포인트부터 mXm 크기의 박스 안에 있는 파리 개수를 세주는 killCounter() 함수를 만들었다.

rowStart, colStart는 제일 왼쪽 위 모서리의 좌표다. 5x5 크기 배열에 2x2 파리채를 rowStart=1, ColStart=1에 적용한다면 다음과 같을 것이다.

array[i][j]를 i가 rowStart부터 rowStart+m까지일 때, 각각의 경우에 대해 j가 colStart부터 colStart+m까지 일 때 더해준다. 즉 위와 같은 예라면, (1,1), (1,2), (2,1), (2,2)의 좌표 내부의 값을 더해준다.

메인 함수 내부에는 테스트 케이스에 대해 배열을 만들고, killCounter() 함수를 가능한 모든 rowStart와 colStart에 대해 적용해 그 수를 비교한다.

kill=0으로 시작하고, 맨 처음 killCounter() 함수를 사용해 리턴된 값을 넣어준다. 이후 돌리는 killCounter() 함수의 리턴값은 kill 보다 크면 kill에 넣어주고, 아니면 버린다.

최종적으로 kill 변수 안에 들어있는 값을 출력한다.