글 읽기 - 사다리조작 내부 흐름 관련 질문

cesta123 5년 전 0

해결은 하였으나 이해가 되질 않아서 질문드립니다.
기존에 코드 16번째 줄 부터 24번 째 줄 사이는
while (x <= H){
if (a[x][y - 1] == 1){
y -= 1; x+=1;
}
else if (a[x][y] == 1){
y += 1; x+=1;
}
else if(a[x][y] == 0) x += 1;
}
이거였을 때 시간초과가 났었는데 지금 글처럼 해당부분을 바꾸니까 시간초과가 나지 않고 해결되었습니다. 그런데 이해가 잘 되지를 않아서 질문드립니다. 지금 윗 코드에 있는 상태로도 a[x][y] = 0 or 1값만 갖게 되고 문제없이 H까지 내려간다고 생각하는데요. 지금 윗 코드와 같은 방식 과 바뀐 코드간에 어떤 차이가 있는건가요? 어차피 x를 한칸 더해주는데 이해가 되지를 않습니다.

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

int N, M, H; // N :col, H :row , 뒤 바뀜

int a[32][12];
int ans;

void solve(int cnt){
	bool ok = false;
	for (int j = 1; j < N; j++){
		int x = 0, y = j;
		while (x <= H){ // 해당 세로선 시작에서 H까지 갔을 때 j와 일치하는지
			if (a[x][y - 1] == 1){
				y -= 1;
			}
			else if (a[x][y] == 1){
				y += 1;
			}
			x += 1;
		}

		if (y != j){
			ok = true;
		}
		if (ok) break;
	}

	if (!ok){
		if (ans > cnt) ans = cnt;
	}
}

void check(int n, int cnt){

	if (cnt > n){
		return;
	}

	else if (cnt == n){
		solve(cnt);

		return;
	}

	for (int j = 1; j < N; j++){ // j=N일 때 a[i][N] 에서는 오른쪽 이동이 불가하므로 놓지 않음.
		for (int i = 1; i <= H; i++){
			if (a[i][j] != 0 || a[i][j - 1] != 0 || a[i][j + 1] != 0) continue; // 인접한 곳에 다리 놓을 수 없음
			else{
				a[i][j] = 1;

				check(n, cnt + 1);

				a[i][j] = 0;
			}
		}
	}
}

int main(){
	cin >> N >> M >> H;

	for (int i = 0; i < M; i++){
		int x, y;
		cin >> x >> y;
		a[x][y] = 1;
	}

	ans = 2147483647;

	solve(0); // 한 개도 안놨을 때 답인지

	if (ans == 0){
		cout << ans << '\n';
	}
	else{
		for (int k = 1; k <= 4; k++){ // 4개 이상은 break;
			if (k == 4) break;
			check(k, 0);
			if (ans != 2147483647) break;
		}
		if (ans == 2147483647) ans = -1;

		cout << ans << '\n';
	}
}

cesta123 5년 전 0

글쓴이입니다. 이 코드가 시간이 1960~1968ms가 나오는데 문제 제한이 2초여서 간당간당했습니다. 혹시 else if(a[x][y] == 0) 이 확인을 너무 많이해서 시간이 더 걸릴수도 있을까요? 고수님들 부탁드립니다. ㅜ

cesta123 5년 전 1

혹시나 보실 분들을 위해 셀프 댓글 답니다. 현재 코드는 1개 놓아보고 모든 곳 돌아보고 답 안나오면, 새로운 상태에서 2개씩 놓고 모든 곳 돌아보고 답 안나오면, 다시 새로운 상태에서 3개씩 놓고 모든 곳 돌아보고를 반복합니다. 현재 코드에서 우선 문제의 놓여진 사다리를 제외한 빈칸들을 후보를 2차원 벡터로 좌표들을 push 한 다음에 빈칸 후보들만 돌리면서 1개 놓고, 유지한 상태로 for문2번째 가보고, 다시 유지한 상태로 for문3번째 가보고 방식으로 했더니 400ms까지 줄일수 있었고 제가 질문했던 while문 안의 두가지 경우 둘다 답이 되는것을 보아 로직에는 차이 없었습니다. 정말 2초 이내에 간당간당하게 풀었던지라 else if 조건 불필요한 추가로 시간 초과가 났다고 생각합니다.

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

문제

문제

출처

ICPC

사다리조작 내부 흐름 관련 질문

cesta123 5년 전 0

cesta123 5년 전 0

cesta123 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말