파리 퇴치 C++, Python(SW Expert Academy)

난이도 : D2

문제번호 : 2001

※ 저의 풀이가 무조건적인 정답은 아닙니다.

다른 코드가 좀더 효율적이고 좋을 수 있습니다.

다른사람들의 풀이는 언제나 참고만 하시기 바랍니다.

문제 주소 및 출처입니다.

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

 

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

---

1. 문제 설명

N x N 배열 안의 숫자는 해당 영역에 존재하는 파리의 개수를 의미한다. 아래는 N=5 의 예이다.

1	3	3	6	7
8	13	9	12	8
4	16	11	12	6
2	4	1	23	2
9	13	4	7	3

M x M 크기의 파리채를 한 번 내리쳐 최대한 많은 파리를 죽이고자 한다. 죽은 파리의 개수를 구하라! 예를 들어 M=2 일 경우 위 예제의 정답은 49마리가 된다.

1	3	3	6	7
8	13	9	12	8
4	16	11	12	6
2	4	1	23	2
9	13	4	7	3

입력

가장 첫 줄에는 테스트 케이스의 개수 T가 주어지고, 그 아래로 각 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 번째 줄에 N 과 M 이 주어지고, 다음 N 줄에 걸쳐 N x N 배열이 주어진다.

출력

출력의 각 줄은 '#t'로 시작하고, 공백을 한 칸 둔 다음 정답을 출력한다. (t는 테스트 케이스의 번호를 의미하며 1부터 시작한다.)

예시

입력	출력
10 5 2 1 3 3 6 7 8 13 9 12 8 4 16 11 12 6 2 4 1 23 2 9 13 4 7 3 6 3 29 21 26 9 5 8 21 19 8 0 21 19 9 24 2 11 4 24 19 29 1 0 21 19 10 29 6 18 4 3 29 11 15 3 3 29 ...	#1 49 #2 159 ...

 

1번째 케이스는 아무 것도 사지 않는 것이 최대 이익이다. 2번째 케이스는 1,2일에 각각 한 개씩 사서 세 번째 날에 두 개를 팔면 10의 이익을 얻을 수 있다.

 

---

2. 문제풀이

문제를 풀때 일정공간에 파리채 크기 만큼의 파리를 완전탐색으로 찾으면 된다고 생각했습니다. 그래서 위에서부터 오른쪽으로 끝까지 갔다면 한칸내려가서 오른쪽으로 이동하면서 순차적으로 탐색을하고 제일큰수를 저장하여 최종적으로 큰값을 반환하도록 했습니다.   따라서 1,2차 반복문에서는 오른쪽 아래로 이동하는 반복문이 됐고, 3,4차 반복문에서는 영역안에 파리의 합을 구하는 반복문입니다. ------------------------------------------------ 추가내용 파이썬으로도 풀어보았습니다. 누적합이라는 개념을 이용하여 3차반복문에서 끝내도록 만들었습니다.

 

---

3. 소스코드

#include <iostream>
#include <string>
 
using namespace std;
 
int main(){
    //총 반복길이, 칸넓이, 파리채크기, 최대리스트
    int length, n, m, list[15][15];
    cin >>length;
    //총 반복만큼
    for(int i=1; i<=length; i++){
        int max = 0;
        cin >> n >>m;
        //파리개수를 입력받는다.
        for(int j=0; j<n; j++){
            for(int k=0; k<n; k++){
                cin >> list[j][k];
            }        
        }
        //오른쪽과 아래로 이동하면서 파리수를 더하여 최대파리수 계산
        for(int j=0; j<=n-m; j++){
            for(int k=0; k<=n-m; k++){
                //여기까지가 파리채 이동
                int sum = 0;
                //여기부터가 파리수 더하기
                for(int x =j; x < j+m; x++){
                    for(int y = k; y < k+m; y++){
                        sum += list[x][y];
                    }
                }
                //최대값과 비교하여 더크다면 바꾸기
                if(sum > max)        max = sum;
            }
        }
            cout << "#" << i << " " << max << endl;
    }
    return 0;
}

 

def data_init():
    N, M = map(int, input().split())
    arr = [list(map(int, input().split())) for _ in range(N)]
    sum_arr = [[0 for _ in range(N+1)] for _ in range(N+1)]
    
    for i in range(N):
        for j in range(N):
            sum_arr[i][j+1] = arr[i][j] + sum_arr[i][j]
 
    return N, M, arr, sum_arr
 
 
def solution():
    max_data = 0
    N, M, arr, sum_arr = data_init()
 
    for y in range(N-M+1):
        for x in range(N-M+1):
            data = 0
            for i in range(M):
                data += sum_arr[y+i][x+M] - sum_arr[y+i][x]
            max_data = max(max_data, data)
 
    return max_data
 
 
test_case_size = int(input())
for t in range(test_case_size):
    answer = solution()
    print('#{} {}'.format(t+1, answer))