[BOJ] 1463번 : 1로 만들기

1. problem : 

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

 

2. solution 1:

// Authored by : BaaaaaaaaaaarkingDog
// Co-authored by : -
// http://boj.kr/161694ef04f04d8dbe826e253622c1cb
#include <bits/stdc++.h>
using namespace std;

int d[1000005];
int n;

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n;
  d[1] = 0;
  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];
}

source code 출처 : https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x10/solutions/1463.cpp

basic-algo-lecture/0x10/solutions/1463.cpp at master · encrypted-def/basic-algo-lecture

 

3. solution 2: 

#include <bits/stdc++.h>
using namespace std;
int n;
int board[1000005];
bool isvis[1000005];
queue<int> Q;

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n; 
	board[1] = 0;
	isvis[1] = 1;
	Q.push(1); 
	while (!Q.empty()) {
		int cur = Q.front(); Q.pop(); 
		for (int dir = 0; dir < 3; dir++) {
			int nx = 0;
			if (dir == 0) nx = cur + 1;
			else if (dir == 1) nx = cur * 2;
			else nx = cur * 3; 
			if (nx > n || isvis[nx] != 0) continue; 
			isvis[nx] = 1; 
			board[nx] = board[cur] + 1; 
			Q.push(nx);
		}
	}
	cout << board[n] << '\n';
}

bfs를 이용한 풀이.