글 읽기 - 숨바꼭질 계속 터집니다

ksoosung77 2년 전 0

0부터 80000까지 이정도 하면 계속 컴퓨터가 감당하지 못하고 터져버립니다

저가 뭘 잘못한 건가요?

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#pragma warning(disable:4996)

using namespace std;

int num[100001] = {};
queue<int>arr;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int s, e;
	cin >> s >> e;
	num[s]++;
	if (s < e) {
		arr.push(s);
		int time = 0;
		bool find = false;
		while (arr.size()) {
			int size = arr.size();
			for (int i = 0; i < size; i++) {
				if (arr.front() == e) {
					find = true;
					break;
				}
				if (arr.front() < e && num[arr.front() * 2] == 0) {
					num[arr.front() * 2]++;
					arr.push(arr.front() * 2);
				}
				if (arr.front() < e && num[arr.front() + 1] == 0) {
					num[arr.front() + 1]++;
					arr.push(arr.front() + 1);
				}
				if (0 < arr.front() && num[arr.front() - 1] == 0) {
					num[arr.front() - 1]++;
					arr.push(arr.front() - 1);
				}
				//cout << arr.front()<<" "<<arr.size() << endl;
				arr.pop();
			}
			if (find)break;
			time++;
		}
		cout << time;
	}
	else {
		cout << s - e;
	}
}

wider93 2년 전 1

100000을 넘는 숫자를 배열 인덱싱하고 있지 않은지 확인해보세요.

ksoosung77 2년 전 0

헐

arr.front()*2 <= 100000 이렇게 했더니 풀리네요 ㄷㄷ

그런대 만약 100000을 넘고 -로 내려가서 더 빨리 갈 수 있는 숫자도 있을 수 있지 않나요?

왜 무조건 100000을 넘지 못하나요?

wider93 2년 전 5

좋은 포인트입니다.

a -> 2a -> 2a-1 -> 2a-2 보다

a-> a-1 -> 2a-2가 더 빠르기 때문에, 그리고 100000이 2의 배수이기 때문에, 100000을 초과하는 경로를 고려하지 않아도 답이 나옵니다. 해당 부분을 고려하지 않은 사람을 저격할 수 있게, 2배 대신 3배 등으로 바뀐 문제가 하나쯤 있으면 좋을 것 같긴 합니다.

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

문제

문제

출처

ICPC

숨바꼭질 계속 터집니다

ksoosung77 2년 전 0

wider93 2년 전 1

ksoosung77 2년 전 0

wider93 2년 전 5

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말