Baekjoon 1463 1로 만들기

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

소스결과 2964KB / 0ms

출처 Baekjoon

언어 C++17

분류 다이나믹프로그래밍, BFS

 

설명

주어진 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;
}