글 읽기 - 시간초과 해결방법을 모르겠습니다...

jemin9312 5년 전 0

이런식으로 코드를 작성하여 보았는데 시간초과가 나네요 무엇때문일까요...?

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int n, m;
int map[501][501];
bool check[501][501];
int mx = 0;
int sub_max = 0;
int ver_max = 0;

void ver(int x, int y, int cnt, int sum) {
	//ㅗ
	int sum1 = 0;
	if (y - 1 >= 0 && y + 1 < m && x - 1 >= 0)
		sum1 = map[x][y - 1] + map[x][y] + map[x + 1][y] + map[x][y + 1];
	//ㅓ
	int sum2 = 0;
	if (y - 1 >= 0 && x - 1 >= 0 && x + 1 < n)
		sum2 = map[x][y - 1] + map[x][y] + map[x + 1][y] + map[x - 1][y];
	//ㅏ
	int sum3 = 0;
	if (x - 1 >= 0 && x + 1 < n && y + 1 < m)
		sum3 = map[x + 1][y] + map[x][y] + map[x - 1][y] + map[x][y + 1];
	//ㅜ
	int sum4 = 0;
	if (y - 1 >= 0 && y + 1 < m && x + 1 < n)
		sum4 = map[x][y - 1] + map[x][y] + map[x + 1][y] + map[x][y + 1];

	ver_max = max({ sum1,sum2,sum3,sum4 });

}



void dfs(int x, int y,int cnt,int sum) {

	if (x < 0 || y < 0 || x >= n || y >= m || check[x][y] == true || cnt > 4)
		return;

	if (cnt == 4) {
		if (sub_max < sum)
			sub_max = sum;
		return;
	}
	if (check[x][y] == false) {
		check[x][y] = true;
		dfs(x + 1, y, cnt + 1, sum + map[x + 1][y]);
		dfs(x - 1, y, cnt + 1, sum + map[x - 1][y]);
		dfs(x, y + 1, cnt + 1, sum + map[x][y + 1]);
		dfs(x, y - 1, cnt + 1, sum + map[x][y - 1]);
		check[x][y] = false;
	}

}




int main() {
	

	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf("%d", &map[i][j]);
		}
	}


	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			memset(check, false, sizeof(check));
			sub_max = 0;
			ver_max = 0;
			dfs(i, j,1,map[i][j]);
			memset(check, false, sizeof(check));
			ver(i, j, 1, map[i][j]);
			if (mx < max(sub_max,ver_max))
				mx = max(sub_max,ver_max);
		}
	}

	printf("%d\n", mx);

	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간초과 해결방법을 모르겠습니다...

jemin9312 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말