문제

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

뭐 이딴 문제임. 일단 나는 BFS를 강의를 들으면서 배웠음.

하지만 문제를 보자마자 드는생각은 BFS가 먼저 생각이 났지만 뭘 어떻게 해야할지는 몰랐고,

DP는 아예 생각도 안남. 일단 구글링하면서 남이 짠 코드들 중에서 그나마 제일 이해하기 쉬운 코드로 내 코드와 함께 비교해가며 분석해서 이해함.

https://codingnotes.tistory.com/125

이 블로그에서의 코드에서 parent를 추적할 수 있도록 조금 변경함

그리고 이 문제를 BFS로 풀려면 BFS가 뭔지 정확하게 이해를 할 필요가 있음.

가령 queue에 push를 계속 하는 부분이라던가...

https://velog.io/@starkshn/BFS
내가 정리한 BFS

BFS

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

int n;

vector<bool>	discovered(1000001, 0);

int BFS(int here)
{
	// 누구에게 발견되었는지?
	vector<int>		parent(1000001, -1);

	// 시작점에서 얼만큼 떨어저 있는지?
	vector<int>		distance(1000001, -1);

	queue<int> q;
	q.push(here);
	discovered[here] = here;

	distance[here] = 0;
	parent[here] = here;

	while (q.empty() == false)
	{
		here = q.front(); q.pop();

		// 종료 조건
		if (here <= 1)
		{
			return distance[here];
		}

		if (here % 3 == 0 && discovered[here / 3] == false)
		{
			// 3으로 나누어 떨어지는 경우
			q.push(here / 3);
			discovered[here / 3] = true;
			distance[here / 3] = distance[here] + 1;
			parent[here / 3] = parent[here];
		}

		if (here % 2 == 0 && discovered[here / 2] == false)
		{
			// 2로 나누어 떨어지는 경우
			q.push(here / 2);
			discovered[here / 2] = true;
			distance[here / 2] = distance[here] + 1;
			parent[here / 2] = parent[here];
		}

		if (discovered[here - 1] == false)
		{
			// -1 하는 경우
			q.push(here - 1);
			discovered[here - 1] = true;
			distance[here - 1] = distance[here] + 1;
			parent[here - 1] = here;
		}
	}
}

int main()
{
	cin >> n;
	
	int count = BFS(n);
	cout << count;

	return 0;
}

큐를 사용을 하니까 종료조건에 가장 먼저 걸리는 놈이 있을 것이다.

DP

DP로 푸는 방법은 나중에 공부하고나서 올리도록 하겠다.