[BOJ] 1463번 1로 만들기

소요시간 : 10분

오늘의 몸풀기 문제다.
매우 당연하게 BFS 로 풀이하는 문제라고 생각했는데, 공식 유형은 DP 이다.
질문게시판에 가도 DP로 푼 사람들이 대부분이다.

나는 DP를 잘 못해서 BFS로 풀었나보다 . . .

전체코드

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

int N;
queue<pair<int, int>> Q; // N, time

void Input() {
	cin >> N;
	Q.push({ N, 0 });
}

void Bfs() {

	while (!Q.empty()) {

		int curr = Q.front().first;
		int time = Q.front().second;
		Q.pop();

		if (curr == 1) {
			cout << time << endl;
			return;
		}


		if (curr % 3 == 0) {
			Q.push({ (curr / 3), time + 1 });
		}

		if (curr % 2 == 0) {
			Q.push({ (curr / 2), time + 1 });
		}

		Q.push({ curr - 1, time + 1 });

	}

	return;
}


int main() {

	Input();
	Bfs();

}