문제
홍익이는 홍익대학교 프로그래밍 경진대회의 출제진이다. 홍익이는 새벽에 문제를 만들던 도중 뒤통수에 느껴지는 고통과 함께 정신을 잃었다.
홍익이는 좁은 방에서 눈을 떴다. 주변을 살펴보니 벽면에는 LED로 된 다섯 자리 십진수 N이, 그 옆에 T, G라는 알파벳과 함께 또 다른 정수 두 개가 쓰여 있었고, 벽 앞에는 버튼 A, B 두 개가 있었다.
버튼을 이리저리 눌러보던 똑똑한 홍익이는 어떻게 해야 방을 탈출할 수 있을지 금방 눈치챘다.
버튼과 수에 대해 홍익이가 알아낸 것은 다음과 같다.
- 버튼 A를 누르면 N이 1 증가한다.
- 버튼 B를 누르면 N에 2가 곱해진 뒤, 0이 아닌 가장 높은 자릿수의 숫자가 1 줄어든다. 예를 들어 123→146으로, 5→0으로, 3→5로 변한다. 단, N이 0이면 버튼 B를 눌러도 수가 변하지 않는다.
- LED가 다섯 자리까지밖에 없기 때문에 N이 99,999를 넘어가는 순간 탈출에 실패하게 된다.
- 버튼 B를 눌러 N에 2를 곱한 순간 수가 99,999를 넘어간다면, 높은 자릿수의 수를 1 낮췄을때 99,999를 넘지 않는다고 해도 탈출에 실패하게 된다.
또한 홍익이는 최대 T회 버튼을 누를 수 있고, 그 횟수 안에 LED로 표현된 N을 G와 같게 만들어야 탈출할 수 있다는 사실을 알아냈다.
똑똑한 홍익이는 이와중에 자존심이 발동해 버튼 누르는 횟수를 최소로 하여 방을 탈출하기로 했다.
홍익이의 방 탈출을 기원하며, 탈출에 필요한 최소의 버튼 횟수를 구하자.
입력
첫 번째 줄에 N (0 ≤ N ≤ 99,999), T (1 ≤ T ≤ 99,999), G (0 ≤ G ≤ 99,999)가 공백 하나를 사이에 두고 주어진다.
각각 N은 LED로 표현된 수, T는 버튼을 누를 수 있는 최대 횟수, G는 탈출을 위해 똑같이 만들어야 하는 수를 뜻한다.
출력
첫 번째 줄에 탈출에 필요한 최소의 버튼 횟수를 출력한다.
만약 탈출할 수 없다면 “ANG”을 따옴표 없이 출력한다.
예제 입력 1
1 7 10예제 출력 1
7예제 입력 2
7142 10 7569예제 출력 2
3예제 입력 3
7142 1 7569예제 출력 3
ANG예제 입력 4
63429 99999 231예제 출력 4
ANG풀이
이 문제는 bfs(너비 우선 탐색) 알고리즘을 이용해서 풀 수 있었다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");
int N = Integer.parseInt(input[0]);
int T = Integer.parseInt(input[1]);
int G = Integer.parseInt(input[2]);
bfs(N, T, G);
}
public static void bfs(int N, int T, int G) {
Queue<Pair> queue = new LinkedList<>();
boolean[] visited = new boolean[100000];
visited[N] = true;
queue.add(new Pair(N, 0));
while(!queue.isEmpty()) {
Pair temp = queue.poll();
if(temp.t>T) break;
if(temp.n==G) {
System.out.println(temp.t);
return;
}
for(int i=0; i<2; i++) {
if(i==0) {
int nx = temp.n+1;
if(nx>99999 || visited[nx]) continue;
visited[nx] = true;
queue.add(new Pair(nx, temp.t+1));
}
else {
int nx = temp.n*2;
if(nx>99999 || nx==0) continue;
int idx = -1;
for(int j=1; j<7; j++) {
if(nx%(int)Math.pow(10, j)==nx) {
idx = j;
break;
}
}
if(idx!=-1) {
nx -= (int)Math.pow(10, idx-1);
if(visited[nx]) continue;
visited[nx] = true;
queue.add(new Pair(nx, temp.t+1));
}
}
}
}
System.out.println("ANG");
}
public static class Pair {
int n;
int t;
public Pair(int n, int t) {
this.n = n;
this.t = t;
}
}
}
👶🏻Jr. Programmer