백준 1463 1로 만들기

백준 1463 1로 만들기

해설

Queue를 이용하여, 임의의 n 에서 1 까지의 이동하는 것을 구현하여서 최단경로 길이를 구할 수 있다. (BFS)

하지만 문제를 뒤집어서 생각해보면, n에서 1까지의 최단경로 길이는 다음 세개 중 하나이다.

1. n/2 에서 1까지 가는 최단경로 길이 + 1
2. n/3 에서 1까지 가는 최단경로 길이 +1
3. n-1 에서 1까지 가는 최단경로 길이 + 1

아래는 memoization을 이용하여 문제를 해결한 소스코드이다.

````C++

#include

#include

#include

using namespace std;
int d[(int)1e6+1];

int go(int cur)
{ if ( cur <= 1 ) return 0;
if ( d[cur] >= 0) return d[cur];

d[cur] = 1e9; 
if ( cur%2 == 0 ) d[cur] = go(cur/2)+1; 
if ( cur%3 == 0 ) d[cur] = min( go(cur/3) +1, d[cur] ); 
d[cur] = min(go(cur-1)+1, d[cur]); 
return d[cur]; 

} int main()
{ ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
memset(d, -1, sizeof(d));

int n;  
cin >> n; 

cout << go(n) << "\n"; 

} `