U E D R , A S I H C RSS

1R/2016_09_23 (rev. 1.3)

1R/2016_09_23



1. 오늘의 문제

2. 참가자

3. 코드

3.1. 15이원준


3.2. 박인서

#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;
}

3.3. 곽정흠


4. 아이디어

4.1. 15이원준


4.2. 박인서

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

4.3. 곽정흠

Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:22:07
Processing time 0.0193 sec