[BOJ] 1463 - 1로 만들기 (C++)

1. 알고리즘

- DP문제
- 이 문제는 BFS 알고리즘으로 풀 수 있는 문제이다. 즉, Queue를 사용하여 문제를 푼다.

2. 전체 소스

#include <iostream> #include <queue> using namespace std; const int MAX = 1000000; int check[MAX+1]; int dist[MAX+1]; int main(){ int n; cin >> n; queue <int> q; q.push(n); check[n] = true; dist[n] = 0; while(!q.empty()){ int now = q.front(); q.pop(); if(now == 1) break; if(now%3 == 0 && check[now/3] == false){ q.push(now/3); check[now/3] = true; dist[now/3] = dist[now] + 1; } if(now%2 == 0 && check[now/2] == false){ q.push(now/2); check[now/2] = true; dist[now/2] = dist[now] + 1; } if(now-1 > 0 && check[now-1] == false){ q.push(now-1); check[now-1] = true; dist[now-1] = dist[now] + 1; } } cout<<dist[1] <<endl; return 0; }

3. 참고 사항

4. 문제

백준 알고리즘 : https://www.acmicpc.net/problem/1463