글 읽기 - 31%에서 틀리다고 합니다...

ksoosung77 2년 전 0

반례좀 알려주세요 ㅠㅜ

2일 소요중

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

using namespace std;

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

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int s, e;
	int time = 0;
	int holjjak = 1;
	cin >> s >> e;
	arr.push(s);
	num[s] = 1;
	while (arr.size()) {
		int size = arr.size();
		if (num[e] != 0 && ((num[e] == holjjak)||num[e]==3)) {
			cout << time << endl;
			return 0;
		}
		//cout << "e:" << e << " " << holjjak << " " << num[e] << endl;
		if (holjjak == 1)holjjak = 2;
		else holjjak = 1;
		while (size--) {
			//cout << arr.front() <<" "<< num[arr.front()] << endl;
			if (arr.front() == e) {
				cout << time << endl;
				return 0;
			}

			if (0 < arr.front()) {
				if (num[arr.front() - 1] == 0) {
					num[arr.front() - 1] = holjjak;
					arr.push(arr.front() - 1);
				}
				else if (num[arr.front() - 1] != 0&& num[arr.front() - 1]!=holjjak) {
					if (num[arr.front() - 1] != 3)num[arr.front() - 1] = 3;
				}
			}

			if (arr.front()<500000) {
				if (num[arr.front() + 1] == 0) {
					num[arr.front() + 1] = holjjak;
					arr.push(arr.front() + 1);
				}
				else if (num[arr.front() + 1] != 0 && num[arr.front() + 1] != holjjak) {
					if (num[arr.front() + 1] != 3)num[arr.front() + 1] = 3;
				}
			}

			if (arr.front()*2 <= 500000) {
				if (num[arr.front() * 2] == 0) {
					num[arr.front() * 2] = holjjak;
					arr.push(arr.front() * 2);
				}
				else if (num[arr.front() * 2] != 0 && num[arr.front() * 2] != holjjak) {
					if(num[arr.front()*2]!=3)num[arr.front() * 2] = 3;
				}
			}

			arr.pop();
		}
		if (e > 500000)break;
		time++;
		e += time;
	}
	cout << "-1\n";
}

ksoosung77 2년 전 0

와 진짜 이 방법까진 하기 싫었는데

a-2

a+2

2a-2

2a-1

2a+1

2a+2

이렇게 해놓고 bfs에

홀 짝 비교해서 풀었네요

불편ㅡㅡㅡㅡㅡㅡㅡㅡ

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

문제

문제

출처

ICPC

31%에서 틀리다고 합니다...

ksoosung77 2년 전 0

ksoosung77 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말