문제
홍익이는 홍익대학교 프로그래밍 경진대회의 출제진이다. 홍익이는 새벽에 문제를 만들던 도중 뒤통수에 느껴지는 고통과 함께 정신을 잃었다.
홍익이는 좁은 방에서 눈을 떴다. 주변을 살펴보니 벽면에는 LED로 된 다섯 자리 십진수 N이, 그 옆에 T, G라는 알파벳과 함께 또 다른 정수 두 개가 쓰여 있었고, 벽 앞에는 버튼 A, B 두 개가 있었다.
![](https://blog.kakaocdn.net/dn/bbCZ8j/btrXIjVv69x/mUu5GbrWpPW2Uzm5jFGSGk/img.png)
버튼을 이리저리 눌러보던 똑똑한 홍익이는 어떻게 해야 방을 탈출할 수 있을지 금방 눈치챘다.
버튼과 수에 대해 홍익이가 알아낸 것은 다음과 같다.
- 버튼 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
0 7 10
출력 1
0
입력 2
0 8 10
출력 2
8
입력 3
23 1 36
출력 3
1
접근
2가지의 버튼 선택지가 있고, 최소한의 거리로 가야하기 때문에 BFS를 채택하였습니다.
그리고 중간중간 갔던길을 제외하여 시간을 아끼기위해 방문체크도 해주었습니다.
코드
import java.util.*;
import java.util.regex.Pattern;
import java.io.*;
public class Main {
static boolean visit[] = new boolean[100000];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int T = Integer.parseInt(st.nextToken());
int G = Integer.parseInt(st.nextToken());
int result = bfs(N, G, T);
if(result == -1) System.out.println("ANG");
else System.out.println(result);
br.close();
}
public static int bfs(int number, int target, int maxTry) {
Queue<int[]> q = new LinkedList<>();
q.add(new int[] {number,0});
while(!q.isEmpty()) {
int[] now = q.poll();
int nowN = now[0];
int cnt = now[1];
//방문한곳
if(visit[nowN]) continue;
visit[nowN] = true;
//버튼누를 수 있는 횟수 초과
if(maxTry < cnt) return -1;
//목적지 도착
if(nowN == target) return cnt;
//값이 99999면 더이상 버튼을 누를 수 없음
if(nowN == 99999) continue;
if(!visit[nowN+1]) q.add(new int[] {nowN+1, cnt+1});
//값이 0이면 두배버튼을 눌러봤자임
if(nowN == 0) continue;
nowN *= 2;
//곱하기 버튼을 눌렀을때 99999가 넘어가면 실패
if(nowN > 99999) continue;
String str = String.valueOf(nowN);
char[] temp = str.toCharArray();
for(int i=0; i<temp.length; i++) {
if(temp[i] =='0') continue;
else {
int num = temp[i] - '0';
temp[i] = String.valueOf(num-1).charAt(0);
str = new String(temp);
int result = Integer.parseInt(str);
if(!visit[result]) q.add(new int[] {result,cnt+1});
break;
}
}
}
return -1;
}
}
주의
목적지에 도달했는지보다, 버튼 누를 수 있는 횟수를 먼저 검사해야 합니다.
'공부 정리 > 백준' 카테고리의 다른 글
[백준] 2233 사과나무 자바 (0) | 2022.07.05 |
---|---|
[백준] 자바 1799 비숍 (0) | 2022.06.22 |
[백준] 자바 16562 친구비 (0) | 2022.06.17 |
[백준] 자바 15900 나무 탈출 (0) | 2022.06.13 |
[백준] 자바 23807 두 단계 최단 경로 3 (0) | 2022.06.03 |
댓글