[C++] 백준 14562번: 태권왕

문제 링크

14562번: 태권왕

문제 요약

S와 T를 같게 만드는 동작의 최소 횟수를 구해야 한다.
다음의 동작은 1회로 취급된다.
1. S에 2를 곱하고 T에 3을 더한다.
2. S에 1을 더한다.

접근 방법

매 단계마다 몇가지 동작을 선택해서 시행할 수 있고, 특정한 결과를 만드는 동작의 최소횟수를 구해야 합니다.

이런 유형의 문제는 너비 우선 탐색 문제가 매우 많기 때문에 손쉽게 해결할 수 있습니다.

단, S가 T보다 커지는 경우, 1번 동작, 2번 동작 중 어떤 것을 하더라도 T가 다시 커질 가능성은 없습니다. 따라서 이러한 경우는 적절한 pruning이 필요합니다. 이를 처리하지 않을 경우 MLE를 받을 가능성이 있습니다.

T값이 증가하는 경우는 1번 동작에서밖에 없습니다. 2번 동작에서는 T가 증가하지 않지만 S는 반드시 증가합니다. 따라서 중복이 발생할 가능성은 낮습니다. 제 경우에도 처음에는 std::set을 이용해서 재방문 처리를 해주었지만, visited를 제거해준 제출에도 AC를 받았습니다.

코드

#include <bits/stdc++.h>

using namespace std;

struct Info {
	int s, t, cnt;
};

int main(void)
{
	int c;
	cin >> c;

	while (c--)
	{
		int s, t;
		cin >> s >> t;

		queue<Info> q;
		q.push({ s, t, 0 });

		while (!q.empty())
		{
			Info now = q.front();
			q.pop();

			if (now.s > now.t)
				continue;

			if (now.s == now.t)
			{
				cout << now.cnt << '\n';
				break;
			}

			Info next = { now.s * 2, now.t + 3, now.cnt + 1 };
			q.push(next);
			next = { now.s + 1, now.t, now.cnt + 1 };
			q.push(next);
		}
	}

	return 0;
}