글 읽기 - 사다리조작 시간초과 문제점 찾아주세요 ㅠㅠ

jinhotoy 2년 전 0

테스트 케이스는 통과하는 걸 확인 했습니다.

근데 시간초과 때문에 발목을 잡힌 상태인데 아무리 봐도 어떻게 수정을 해야할지 감이 안잡힙니다.

도와주세요 ㅠㅠ

#include<cstdio>
int N, M, H, answer = -1, result = 10e9;
int next[271][11];
bool check[271][11];
int go(int h, int c) {//사다리 탄 결과
	if (h > H)
		return c;
	if (next[h][c] == 0)
		go(h + 1, c);
	else
		go(h + 1, next[h][c]);
}
void solve(int height, int cnt) {
	if (height > H) { //사다리 타기
		for (int j = 1; j <= N; j++) {
			int temp = j;
			for (int i = 1; i <= H; i++) {
				if (next[i][j] > 0) {
					temp = go(i + 1, next[i][j]);
					break;
				}
			}
			if (j != temp)
				return;
		}
		if (result > cnt)
			result = cnt;
		return;
	}

	for (int i = 1; i <= N - 1; i++) {
		if (check[height][i] || check[height][i+1]) continue; //사다리 있으면 pass
		
		next[height][i] = i + 1;
		next[height][i + 1] = i;
		check[height][i] = true;
		check[height][i + 1] = true;
		solve(height + 1, cnt + 1); //사다리 건설
		next[height][i] = 0;
		next[height][i + 1] = 0;
		check[height][i] = false;
		check[height][i + 1] = false;
	}

	solve(height + 1, cnt); //해당 height에서 사다리 건설 안함

}
int main()
{
	scanf("%d %d %d", &N, &M, &H);
	for (int i = 0; i < M; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		next[a][b] = b + 1;
		next[a][b + 1] = b;
		check[a][b] = true;
		check[a][b + 1] = true;
	}

	solve(1, 0);

	if (result <= 3)
		answer = result;
	printf("%d\n", answer);
	return 0;
}

jh05013 2년 전 1

https://www.acmicpc.net/board/...

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

문제

문제

출처

ICPC

사다리조작 시간초과 문제점 찾아주세요 ㅠㅠ

jinhotoy 2년 전 0

jh05013 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말