Baekjoon1463-1로 만들기

백준 사이트 1463 - 1로 만들기 문제입니다.

---

1. 문제

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

---

2. Input , Output

---

3. 분류 및 난이도

DP문제입니다.
저는 bfs와 dp를 이용해서 풀었습니다.
백준에서는 sliver3난이도를 책정하고 있습니다.

---

4. 생각한 것들

• 3가지의 경우의 수로 반복되는 문제이므로 dp가 떠오르고 재귀함수가 떠오르는데, 재귀를 잘 못 쓰므로 bfs를 쓰기로 했습니다.
• 로직은 간단했습니다. 3가지 경우의 수 모두 queue에 넣어주고 1을 가장 빨리 pop()할 경우의 count값을 출력해주었습니다.

---

5. code

주석이 없는 것

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

bool* v;

int bfs(int n)
{
	int result = 0;
	queue<pair<int, int>> q;
	q.push(make_pair(n, 0));
	v[n] = true;
	while (!q.empty())
	{
		int temp = q.front().first;
		int count = q.front().second;
		if (temp == 1)
			return count;
		q.pop();
		if (temp % 3 == 0 && v[temp / 3] == false)//나누어 떨어짐.
		{
			v[temp / 3] = true;
			q.push(make_pair(temp / 3, count + 1));
		}
		if (temp % 2 == 0 && v[temp / 2] == false)
		{
			v[temp / 2] = true;
			q.push(make_pair(temp / 2, count + 1));
		}
		if (v[temp - 1] == false)
		{
			v[temp - 1] = true;
			q.push(make_pair(temp - 1, count + 1));
		}
	}
}

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

	int n;
	cin >> n;
	v = new bool[n + 1];
	memset(v, false, sizeof(bool) * n + 1);
	cout << bfs(n);

	return 0;
}

주석이 있는 것

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

bool* v;

int bfs(int n)
{
	int result = 0;
	queue<pair<int, int>> q;
	q.push(make_pair(n, 0));
	v[n] = true;
	while (!q.empty())
	{
		int temp = q.front().first;
		int count = q.front().second;
		if (temp == 1)
			return count;
		q.pop();
		if (temp % 3 == 0 && v[temp / 3] == false)//나누어 떨어짐.
		{
			//cout << "3 " << temp<<" " << count << '\n';
			v[temp / 3] = true;
			q.push(make_pair(temp / 3, count + 1));
		}
		if (temp % 2 == 0 && v[temp / 2] == false)
		{
			//cout << "2 " << temp <<" "<< count << '\n';
			v[temp / 2] = true;
			q.push(make_pair(temp / 2, count + 1));
		}
		if (v[temp - 1] == false)
		{
			//cout <<"1 "<< temp<<" "<<count<<'\n';
			v[temp - 1] = true;
			q.push(make_pair(temp - 1, count + 1));
		}
	}
}

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

	int n;
	cin >> n;
	v = new bool[n + 1];
	memset(v, false, sizeof(bool) * n + 1);
	cout << bfs(n);

	return 0;
}

---

6. 후기

1년 전에 3번 시도해서 틀린 적이 있는데, 이번에는 10분만에 풀어서 기분이 좋았다.