글 읽기 - 왜 시간초과 나는지 답변해주실수 있는분 계실까요....?

leuver 4년 전 0

15684번 사다리문제 질문입니다

이미 사다리가 놓여진곳이 아니면 일단 다 놓아보는 방법으로 구현했습니다. 사다리가 놓여있다는 것은 a[i][j]에 -1이 아닌 숫자가 있으면 사다리라고 표현했구요...

코드의 어느 부분때문에 시간초과가 하는지 질문드립니다ㅠㅠ

#include<iostream>
#include<vector>
using namespace std;
int N, M, H;
int ans = -1;
bool check(vector<vector<int>>&a)
{
	bool b = true;
	for (int j = 1; j <= N; j++)
	{
		int x = 1;
		int y = j;
		while (x < H) 
		{
			if (a[x][y] != -1)
				y = a[x][y];
			x++;
		}
		if (a[x][y] != -1)
			y = a[x][y];
		if (y != j) {
			b = false;
			break;
		}
	}
	return b;
}
void putLadder(vector<vector<int>>&a, int count)
{
	
	if (count > 3)
		return;
	else
	{
		bool b = check(a);
		if (b)
		{
			if (ans == -1 || ans > count)
				ans = count;
		}		
	}
	
	for (int i = 1; i <= H; i++)
	{
		for (int j = 1; j < N; j++)
		{
			if (a[i][j] != -1)
				continue;
			if (a[i][j + 1] != -1)
				continue;
			a[i][j] = j + 1;
			a[i][j + 1] = j;
			putLadder(a, count + 1);
			a[i][j] = -1;
			a[i][j + 1] = -1;
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> N >> M >> H;
	vector<vector<int>>a(H + 1, vector<int>(N + 1, -1));
	while (M--)
	{
		int n, m;
		cin >> n >> m;
		a[n][m] = m + 1;
		a[n][m + 1] = m;
	}
	putLadder(a, 0);
	cout << ans << '\n';
}

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

문제

문제

출처

ICPC

왜 시간초과 나는지 답변해주실수 있는분 계실까요....?

leuver 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말