[백준 골드5] 1107번: 리모컨 - Java
1107번: 리모컨 - Java
https://www.acmicpc.net/problem/1107
문제
수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다.
리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다.
수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오.
수빈이가 지금 보고 있는 채널은 100번이다.
입력
첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주어지며, 같은 버튼이 여러 번 주어지는 경우는 없다.
출력
첫째 줄에 채널 N으로 이동하기 위해 버튼을 최소 몇 번 눌러야 하는지를 출력한다.
예제 입력 1
5457
3
6 7 8
예제 출력 1
6
예제 입력 2
100
5
0 1 2 3 4
예제 출력 2
0
예제 입력 3
500000
8
0 2 3 4 6 7 8 9
예제 출력 3
11117
예제 입력 4
100
3
1 0 5
예제 출력 4
0
예제 입력 5
14124
0
예제 출력 5
5
예제 입력 6
1
9
1 2 3 4 5 6 7 8 9
예제 출력 6
2
예제 입력 7
80000
2
8 9
예제 출력 7
2228
풀이
시도
처음에 떠올린 방법은 n을 앞아서부터 한자리씩 보면서 버튼으로 누를 수 있는 동안은 바로 누른 뒤, 누를 수 없는 숫자가 나온 자리의 한 자리 전부터 근처 숫자를 탐색하도록 하는 방식이었는데, n=5_일 때 십의 자리 수를 4로 가야 할지 6으로 가야 할지 고민하다 이 발상이 잘못되었음을 알게 되었다 (51->49가 가깝/59->6n이 가깝)
for (int i=idx; i<str.length(); i++){
int diff = 0;
int p = str.charAt(idx)-'0';
while (p-diff>=0 || p+diff<=9){
if (p-diff>=0 && btns[p-diff]) {
cnt++;
break;
} else if (p+diff<=9 && btns[p+diff]) {
cnt++;
break;
}
diff++;
}
}
브루트포스로 푸는 문제인가 궁금해서 다른 분의 풀이를 브루트포스로 푸는 것이 맞았다...
직접 +, -로 눌러야 하는 부분 Math.abs() 사용 유의
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class Main
{
private void solution() throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int m = Integer.parseInt(br.readLine());
boolean[] btns = new boolean[10];
Arrays.fill(btns, true);
if (m>0) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i=0; i<m; i++) {
int broken = Integer.parseInt(st.nextToken());
btns[broken] = false;
}
}
// 100인 경우 바로 종료
if (n==100) {
System.out.println(0);
return;
}
// 100으로부터 +-만으로 이동하는 경우
long minCount = Math.abs(n-100);
// 0~999999 누를 수 있는 조합을 확인
for(int i=0; i<=999999; i++) {
String numStr = String.valueOf(i);
boolean canPress = true;
for(int j=0; j<numStr.length(); j++) {
if(!btns[numStr.charAt(j)-'0']){
canPress = false;
break;
}
}
if (canPress) {
minCount = Math.min(minCount, numStr.length() + Math.abs(n-i));
}
}
System.out.println(minCount);
}
public static void main(String[] args) throws Exception {
new Main().solution();
}
}