글 읽기 - 시간초과의 이유가 있을까요?

freewizard 5년 전 0

안녕하세요,

저도 효율성의 여지가 있다고 생각하지만 잘 찾지 못해서 질문드립니다.

혹시 시간초과를 극복할 효율화가 있을까요?

미리 감사드립니다

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int board[500][500];
int n, m;
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,-1,0,1 };


bool colored(vector<pair<int,int>> & filled, int currx, int curry){
	for (int i = 0; i < filled.size(); i++) {
		if (filled[i].first == currx && filled[i].second == curry) {
			return true;
		}
	}
	return false;
}

int solve(vector<pair<int,int>> filled, int todo, int total) {
	if (todo == 0) {
		return total;
	}

	int ret = 0;
	int currx, curry;

	for (int i = 0; i < filled.size(); i++) {
		for (int k = 0; k < 4; k++) {
			currx = filled[i].first + dx[k];
			curry = filled[i].second + dy[k];
			if (currx > 0 && curry > 0 && currx < n&&curry < m) {
				if (!colored(filled,currx,curry)) {

					filled.push_back(pair<int, int>(currx, curry));
					ret = max(ret, solve(filled, todo - 1, total + board[currx][curry]));
					filled.pop_back();

				}
			}
		}
	}
		
	

	return ret;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> board[i][j];
		}
	}

	vector<pair<int,int>> filled;

	int ret = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			filled.push_back(pair<int, int>(i, j));
			ret = max(ret, solve(filled, 3, board[i][j]));
			filled.pop_back();
		}
	}

	cout << ret << '\n';
	
}

chocokon 5년 전 0

길쭉한 테트로미노나 정사각형 테트로미노가 아닌,

복잡한 형태의 테트로미노는 전부 3*2 크기 안에 들어가있을수밖에 없습니다. 이 것과 마스킹, 이게 결정적인 힌트겠네요.

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

문제

문제

출처

ICPC

시간초과의 이유가 있을까요?

freewizard 5년 전 0

chocokon 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말