글 읽기 - 삼성기출문제 사다리조작 질문있습니다.(시간초과관련)

minjae200 5년 전 0

adj[b][a] = b와 b+1를 연결시키는 사다리를 a번째 자리에 놓는다. (놓이면 true 아니면 false)

main함수에서 사다리를 0개 놓았을때 부터 3개까지 놓았을때를 생각하고 backtracking을 사용하여 구현하였습니다.

9프로정도에서 시간초과가 떴는데 어느부분에서 시간이 오래걸리는지 모르겠어서 질문올립니다.

(수정 사항 ans값을 구햇으면 break)를 추가해도 안됍니다. ㅠㅠ

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

const int MAXsero = 11;
const int MAXgaro = 31;
const int INF = 987654321;
bool adj[MAXsero][MAXgaro];
int N, M, H, ans = INF;
int result[MAXsero];

bool findResult(void)
{
	int idx = 1;
	for (int i = 1; i <= N; i++) {
		int start = i;
		for (int j = idx; j <= H; j++) {
			if (adj[start][j]) {
				start = start + 1;
			}
			else if (adj[start - 1][j]) {
				start = start - 1;
			}
		}
		result[i] = start;
		if (result[i] != i) return false;
	}
	return true;
}

bool check(int n, int h)
{
	if (n == 1) {
		if (!adj[n][h] && !adj[n + 1][h]) return true;
	}
	else if (n == N) {
		if (!adj[n][h] && !adj[n - 1][h]) return true;
	}
	else {
		if (!adj[n][h] && !adj[n - 1][h] && !adj[n + 1][h]) return true;
	}
	return false;
}

void backtracking(int cnt, int depth)
{
    if(ans != INF) return;
	if (depth == cnt) {
		if (findResult()) {
			if (ans > cnt) ans = cnt;
		}
		return;
	}
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= H; j++) {
			if (check(i,j)) {
				adj[i][j] = true;
				backtracking(cnt + 1, depth);
				adj[i][j] = false;
			}
		}
	}
}

int main(void)
{
	scanf("%d %d %d", &N, &M, &H);
	for (int i = 0; i < M; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		adj[b][a] = true;
	}
	for (int i = 0; i < 4; i++){
		backtracking(0,i);
        if(ans!=INF) break;
	}
	if (ans >= INF) printf("-1\n");
	else printf("%d\n", ans);
	return 0;
}

minjae200 5년 전 0

감사합니다.

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

문제

문제

출처

ICPC

삼성기출문제 사다리조작 질문있습니다.(시간초과관련)

minjae200 5년 전 0

minjae200 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말