글 읽기 - 배열의 선언 범위에 관해 질문드립니다.

alvin11 5년 전 0

아래에 dist[]배열로 거리체크와 방문체크를 동시에 진행했습니다.

그런데 dist[100001]로 했을때는 계속 실패했었는데,

왜 dist[200001]로하면 통과가 될까요?

문제에서 N과 K는 각각 0~100,000 범위여서 왜 이런지 궁금합니다.

감사합니다!

//boj 1697
// 숨바꼭질

// Q.
// int dist[200001]; // 10만일떄 안되다가, 20만일떄 통과.. 왜지?

#include <bits/stdc++.h>
using namespace std;

int dx[3]={-1,1,0}; //이동 방향

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N, K;
	cin >> N >> K;

	if(N>=K){
		cout << N-K << '\n';
		return 0;
	}

	int dist[200001]; // 10만일떄 안되다가, 20만일떄 통과.. 왜지?
	fill(dist,dist+200000,-1); // fill쓰는거 연습하자
	queue<int> Q;
	Q.push(N);
	dist[N]=0;


	while(!Q.empty())
	{
		int now = Q.front(); Q.pop();
		if(now ==K)
		{
			cout << dist[now]<<'\n';
			break;
		}
		//cout << "now : "<< now << "now_dist:"<<dist[now]<<'\n';
		for(int dir=0; dir<3; dir++)
		{
			int next = now + dx[dir];
			if(dir==2) next = 2*now; 
			if(next<0 or next >100000) continue;//범위조심
			if(dist[next]>=0) continue;
			Q.push(next);
			dist[next] = dist[now]+1;
		//	cout << "next : "<< next <<"next_dist:"<<dist[next]<<'\n'; 
		}
	}
	return 0;
}

windflower 5년 전 0

십만 근처에서 순간이동 할 수 있어요!!

alvin11 5년 전 0

ㄴ 답변 감사합니다. 그런데 십만 근처에서 순간이동해도 10만 넘어버리면 next 가 범위에서 벗어나서 continue로 넘어가서,
dist배열에는 영향을 주지 않는걸로 보여서 확신이 안서네요ㅠ

windflower 5년 전 0

제 뜻은 100,002정도로 순간이동해서 돌아오는 것이 더 빠른 경우가 있다는 뜻이였습니다.

배열을 십만으로 잡거나 십만이 넘어가는 경우를 무조건 제외해 버린다면 예외케이스가 생길 수 있습니다

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

문제

문제

출처

ICPC

배열의 선언 범위에 관해 질문드립니다.

alvin11 5년 전 0

windflower 5년 전 0

alvin11 5년 전 0

windflower 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말