인프런 커뮤니티 질문&답변

안녕하세요.

51번 문제 강의를 보고 알고리즘을 이해했다고 생각하고 코드를 스스로 다시 작성했습니다.

그리고 80점이 맞았고, 5번에서 타임 리밋이 발생하였습니다.

답안코드를 다시 읽어보면서 반복문에서 인덱스 부분에서의 차이점이 조금 있고 외에는 같은 알고리즘이라고 생각되는데요.

왜 제 코드는 5번에서 타임 리밋 발생하는지 알고싶습니다.

#include <iostream>

#include <fstream>

using namespace std;

int board[702][702];

int dir[702][702];

int main() {

//ifstream cin;

//cin.open("input.txt");

int width, heigh;

cin >> heigh >> width;

for (int i = 1; i <= heigh; i++) {

for (int j = 1; j <= width; j++) {

cin >> board[i][j];

dir[i][j] = board[i][j] + dir[i - 1][j] + dir[i][j - 1] - dir[i - 1][j - 1];

}

}

int w, h;

cin >> h >> w;

int max = 0;

int num;

for (int i = 0; i < heigh - h + 1; i++) {

for (int j = 0; j < width - w + 1; j++) {

num = dir[i + h][j + w] - dir[i + h][j] - dir[i][j + w] + dir[i][j];

if (max < num)

max = num;

}

}

cout << max;

}