[BOJ] 1463_1로 만들기 with cpp

# 생각

BFS로 작성하게되면 dist값 초기 0에서 *2, *3, +1을 하여 해결할 수 있다

 

DP를 이용하면 짧은 코드로 해결이 가능하다

초기값 : d[1] = 0

점화식 : i = 2 부터 n까지 for문을 돌면서 d[i]를 d[i-1] + 1, d[i/2] + 1, d[i/3] + 1을 가지고 갱신

 

 

# 전체 코드

#include <bits/stdc++.h>
using namespace std;

int d[1111111];
int n;

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

	cin >> n;
	for (int i = 2; i <= n; i++)
	{
		d[i] = d[i - 1] + 1;
		if (i % 2 == 0) d[i] = min(d[i], d[i / 2] + 1);
		if (i % 3 == 0) d[i] = min(d[i], d[i / 3] + 1);
	}
	cout << d[n];
}

 

---

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

1463번: 1로 만들기