-
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
해결됨
선생님, 3중 for 문으로 만든 것 같은데 TimeLimit 에 걸립니다.
20.04.01 21:43 작성 조회수 132
0
문제를 처음 보자마자 4중 for문을 생각했지만, 4중 for 문은 large 에 쓰이지 못 할 것 같아서 조금 고민해서 나름 3중for 문으로 만들었다고 생각했는데 3번 case 까지는 success 이지만 4번부터 Time Limit 이 걸립니다.
충분히 고민했다고 생각하지만 원인을 못 찾겠어서 질문 올립니다 ㅠㅠ
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
using namespace std;
// global variable
int territory[5][50];
// function
// main
int main(int argc, char** argv) {
// input
int i, j ,k;
int h, w, my_h, my_w, sum = 0, pos_h, pos_w, max = -2147000000;
scanf("%d %d", &h, &w);
for (i = 0; i < h; i++)
for (j = 0; j < w; j++)
scanf("%d", &territory[i][j]);
scanf("%d %d", &my_h, &my_w);
// algorithm
for (i = 0; i <= h - my_h; i++) {
sum = 0;
// 처음 내 영역의 sum 을 구한다.
for (pos_h = i; pos_h < i + my_h; pos_h++) {
for (pos_w = 0; pos_w < my_w; pos_w++) {
sum += territory[pos_h][pos_w];
}
}
if (max < sum) max = sum;
// 한칸씩 오른쪽으로 이동해가면서 합을 구한다.
for (j = 0; j <= w - my_w; j++) {
for (pos_h = i; pos_h < i + my_h; pos_h++) {
// 왼쪽을 뺀다.
sum -= territory[pos_h][j];
// 오른쪽을 더한다.
sum += territory[pos_h][j+my_w];
}
if (max < sum) max = sum;
}
}
// print(needed)
printf("%d", max);
// exit
return 0;
}
it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
50. 영지 (territory) 선택 (small : 2차원 배열 브루트포스)
강의실 바로가기
답변을 작성해보세요.
1
0
답변 2