BOJ11403 1로 만들기
문제
정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
- X가 3으로 나누어 떨어지면, 3으로 나눈다.
- X가 2로 나누어 떨어지면, 2로 나눈다.
- 1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.
해설
문제의 규칙을 점화식으로 표현하자면 다음과 같다.
$
\mathrm{D}(i) = \begin{cases}
D[i-1]+1 \
min(D[i],D[i/2]) & i\pmod2 = 0 \
min(D[i],D[i/3]) & i\pmod3 = 0
\end{cases}
$
접근방식 1 (dp)
#include <iostream>
using namespace std;
int dp[1000000]={};
int main(){
int n;
cin >> n;
for(int i=2; i<=n; i++){
dp[i] = dp[i-1]+1;
if(!(i%3))dp[i]=min(dp[i],dp[i/3]+1);
if(!(i%2))dp[i]=min(dp[i],dp[i/2]+1);
}cout << dp[n];
}
접근방식 2 (bfs)
#include <bits/stdc++.h>
using namespace std;
int x,a[1000001]={};
bool seen[1000001]={};
queue<int> q;
void bfs(int i){
if(seen[i]||i==0)return;
seen[i]=true;
if(i==1){
q = queue<int>();
return;
}if(i%3==0){
if(a[i/3]==0)a[i/3]=a[i]+1;
else a[i/3]=min(a[i/3],a[i]+1);
q.push(i/3);
}if(i%2==0){
if(a[i/2]==0)a[i/2]=a[i]+1;
else a[i/2]=min(a[i/2],a[i]+1);
q.push(i/2);
}if(i-1>0){
if(a[i-1]==0)a[i-1]=a[i]+1;
else a[i-1]=min(a[i-1],a[i]+1);
q.push(i-1);
}
}
int main(){
cin >> x;
q.push(x);
while(!q.empty()){
int i=q.front();
q.pop();
bfs(i);
}
cout << a[1];
}