문제
세종대왕은 현수에게 현수가 다스릴 수 있는 영지를 하사하기로 했다. 전체 땅은 사각형으로 표 시된다. 그 사각형의 땅 중에서 세종대왕이 현수가 다스릴 수 있는 땅의 크기(세로의 길이와 가 로의 길이)를 정해주면 전체 땅 중에서 그 크기의 땅의 위치를 현수가 정하면 되는 것이다.
전체 땅은 사각형의 모양의 격자로 되어 있으며, 그 사각형 땅 안에는 많은 오렌지 나무가 심 겨져 있다. 현수는 오렌지를 무척 좋아하여 오렌지 나무가 가장 많이 포함되는 지역을 선택하 고 싶어 한다. 현수가 얻을 수 있는 영지의 오렌지 나무 최대 개수를 출력하는 프로그램을 작 성하세요. 다음과 같은 땅의 정보가 주어지고, 현수가 하사받을 크기가, 가로 2, 세로 3의 크 기이면 가장 많은 오렌지 나무가 있는 영지는 총 오렌지 나무의 개수가 16인 3행 4열부터 시 작하는 구역이다.
💡 입력설명
첫 줄에 H(세로길이)와 W(가로길이)가 입력된다. (5<=H, W<=50) 그 다음 H줄에 걸쳐 각 사 각형 지역에 오렌지의 나무 개수(1~9개) 정보가 주어진다.
그 다음 영지의 크기인 세로길이(1~H)와 가로길이(1~W)가 차례로 입력된다.
💡 출력설명
첫 줄에 현수가 얻을 수 있는 오렌지 나무의 최대 개수를 출력한다.
💡 입력예제
6 7
3 5 1 3 1 3 2
1 2 1 3 1 1 2
1 3 1 5 1 3 4
5 1 1 3 1 3 2
3 1 1 3 1 1 2
1 3 13 1 2 2
2 3
💡 출력예제
16
코드
첫 번째 풀이
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int h, w, p_h, p_w, index, i, j, k, max = -2147000000, sum;
scanf("%d %d", &h, &w);
vector<vector<int> >a(h + 1, vector<int>(w + 1, 0));
for(i = 1; i <= h; i++) {
for(j = 1; j <= w; j++) {
scanf("%d", &a[i][j]);
}
}
// 현수가 하사받을 크기
scanf("%d %d", &p_h, &p_w);
vector<int> dx;
vector<int> dy;
index = p_h * p_w;
for(i = 0; i < p_h; i++) {
for(j = 0; j < p_w; j++) {
dx.push_back(j);
dy.push_back(i);
}
}
// 현수가 하사받을 크기 만큼 2차원 배열 탐색
for(i = 1; i <= h - p_h + 1; i++) {
for(j = 1; j <= w - p_w + 1; j++) {
sum = 0;
for(k = 0; k < index; k++) {
sum += a[i + dy[k]][j + dx[k]];
}
if(sum > max) {
max = sum;
}
}
}
printf("%d", max);
return 0;
}
설명
사용자로부터 h, w를 입력받고 h, w크기의 2차원 배열을 선언하고 2중 for문을 통해 해당 배열의 값을 입력받아 할당한다.
현수가 하사받을 크기 p_h와 p_w를 입력받고 배열을 탐색해야 하므로 dx, dy를 선언하여 해당 크기만큼의 index를 할당해놓는다.
2차원 배열을 탐색하기 위해 행은 1을 시작으로 h - p_h + 1만큼 반복하고 열은 1을 시작으로 w - p_w + 1만큼 반복한다.
하사받은 크기 만큼 탐색하기 위해 k는 0을 시작으로 p_h * p_w(=index) 만큼 반복하여 해당 값들을 변수 sum에 더해나간다.
이후 sum 값이 max보다 클 경우 max에 sum을 할당하고 다음 index에서는 sum을 0으로 초기화 하여 반복한다.
마지막으로 가장 큰 값을 출력하기 위해 max를 출력하여 마무리한다.
해당 내용은 김태원님의 'it 취업을 위한 알고리즘 문제풀이' 강의를 듣고 작성한 글입니다.
