1R/2016 09 23

오늘의 문제

• [1]

참가자

• 박인서
• 곽정흠

코드

박인서

#include <iostream>
#include <queue>
typedef std::pair<int, int> pair_int;
std::queue<pair_int> q;
bool visit[200001];

int main()
{
	int s, e;
	std::cin >> s >> e;
	if (s < e) {
		q.push(pair_int(s, 0));
		while (q.front().first != e) {
			pair_int tq = q.front();
			if (tq.first < e && !visit[tq.first * 2])
				q.push(pair_int(tq.first * 2, tq.second + 1)), visit[tq.first * 2] = true;
			if (tq.first < e && !visit[tq.first + 1])
				q.push(pair_int(tq.first + 1, tq.second + 1)), visit[tq.first + 1] = true;
			if (tq.first > 0 && !visit[tq.first - 1])
				q.push(pair_int(tq.first - 1, tq.second + 1)), visit[tq.first - 1] = true;
			q.pop();
		}

		std::cout << q.front().second;
	}
	else std::cout << s - e;
	return 0;
}

아이디어

박인서

• 기본적인 아이디어는 Queue를 이용한 BFS이다.
• 단 너무 숫자가 커지면 안되므로, 200000이 넘어가면 제한을 한다.
• 그리고 뒤로 갈 경우 갈 수 있는 방법은 -1밖에 없으므로 그 것을 예외 처리 해준다.