[BOJ] 1463 1로 만들기

Link https://www.acmicpc.net/problem/1463

Note

주어진 n을 특정 연산을 통해 1로 만드는 횟수의 최소값을 구한다.

문제 분류가 DP지만 BFS로 해결된다. 결과값이 최대 10만이기때문에 가능한것 같다.
3으로 나눈경우, 2로 나눈경우, 1 뺀 경우 3개로 나누어서 BFS를 진행한다.

알고리즘

1. n을 입력 받는다.
2. n을 Queue에 넣은 후 방문 처리한다.
3. Queue에서 원소를 꺼낸후 3으로 나눈경우, 2로 나눈경우, 1로 나눈경우를 연산하고 방문하지 않은 값이면 nextQueue에 넣는다.
4. Queue의 원소가 없다면 nextQueue의 원소를 전부 Queue로 옮긴 후 3번을 반복한다.
5. 원소가 1이면 시도 횟수를 출력 후 종료한다.

소스코드

#include <iostream>
#include <queue>

using namespace std;

const int MAX = 1000000;

bool check[MAX + 1];

int main()
{
	int n;
	int res = 0;
	bool isOver = false;
	queue<int> q;
	queue<int> nextQ;

	cin >> n;

	q.push(n);
	check[n] = true;

	while (!isOver)
	{
		while (!q.empty())
		{
			int cur = q.front();
			q.pop();

			if (cur == 1)
			{
				isOver = true;
				break;
			}

			if (cur % 3 == 0 && cur / 3 != 0 && !check[cur / 3])
			{
				check[cur / 3] = true;
				nextQ.push(cur / 3);
			}

			if (cur % 2 == 0 && cur / 2 != 0 && !check[cur / 2])
			{
				check[cur / 2] = true;
				nextQ.push(cur / 2);
			}

			if (cur - 1 > 0 && !check[cur - 1])
			{
				check[cur - 1] = true;
				nextQ.push(cur - 1);
			}
		}

		if (isOver)
			continue;

		while (!nextQ.empty())
		{
			q.push(nextQ.front());
			nextQ.pop();
		}

		res++;
	}

	cout << res;

	return 0;
}

2019-04-01 00:42:05에 Tistory에서 작성되었습니다.