[Silver 3] 1463번 1로 만들기

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

1463번: 1로 만들기

 

이 문제는 BFS를 사용해서 해결할 수 있다.

현재 queue에 있는 값이 1이면 연산 횟수를 저장하고 반복을 멈춘다.

값이 3으로 나눠 떨어지거나 2로 나눠 떨어지면 queue에 값을 3이나 2로 나누고 연산 횟수를 저장한다.

또한 값을 1로 뺀 값과 연산 횟수를 저장한다.

 

#include <iostream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;

int x, result;
queue<pair<int,int>> q;

void bfs() {
	q.push(make_pair(x,0));

	while (!q.empty()) {
		int value = q.front().first;
		int counter = q.front().second;
		q.pop();

		if (value == 1) {
			result = counter;
			break;
		}

		if (value % 3 == 0) q.push(make_pair(value/3, counter + 1));

		if (value % 2 == 0) q.push(make_pair(value / 2, counter + 1));

		q.push(make_pair(value - 1, counter + 1));
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> x;
	bfs();
	cout << result << '\n';
}