코딩테스트-알고리즘/백준 BOJ
[백준 BOJ/Silver III] 1463번 : 1로 만들기
닉네임생각즁
2024. 3. 6. 20:13
https://www.acmicpc.net/problem/1463
가능한 경우들을 확인하며 1을 만났을때 이동한 최소의 수(num[1]-1)를 최종 답으로 출력하면 된다
최종 코드
package boj1463;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
public class Main {
static int N;
static int[] num;
static Deque<Integer> dq = new ArrayDeque<>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
num = new int[N+1];
num[N] = 1;
dq.addLast(N);
bfs();
System.out.println(num[1]-1);
}
static void bfs() {
while(!dq.isEmpty()) {
int x = dq.pollFirst();
if(x % 3 == 0) {
int nx = x / 3;
if(num[nx] == 0) {
num[nx] = num[x] + 1;
dq.addLast(nx);
}
}
if(x % 2 == 0) {
int nx = x / 2;
if(num[nx] == 0) {
num[nx] = num[x] + 1;
dq.addLast(nx);
}
}
if(x-1 >= 1) {
int nx = x - 1;
if(num[nx] == 0) {
num[nx] = num[x] + 1;
dq.addLast(nx);
}
}
if(num[1] != 0) return;
}
}
}