관련글
완전 탐색 관련 포스팅은 여기를 참조
1. 개요
문제의 링크는 여기를 참조
문제의 내용은 아래의 더보기를 클릭하여 참조
현재 채널(100)에서 다른 채널로 이동 시 최소로 버튼을 눌러 이동하는 경우를 구하는 문제
2. 풀이
현재 100번에 위치한 상태에서 N번 채널로 리모컨을 눌러 이동하는데, +/- 버튼 또는 숫자 버튼만 누를 수 있다.
알아둬야 할 사항은 다음과 같다.
① + / - 버튼을 누르면 1 채널씩 이동하며 -는 0번까지, +는 무한대로 이동할 수 있다.
② 숫자버튼은 누르면 바로 그 채널로 이동되니 +/-를 누른 후 숫자를 누르는 것은 의미가 없다.(숫자가 먼저!)
③ 고장난 버튼은 누를 수 없다.
여기서 N번 채널이라고 할 때, N은 최대 50만이므로 모든 0~9버튼이 고장났다고 가정했을 때, 현재 100번에서 +만 눌러서 50만으로 가는 것이 최대일 것이다.
하지만 만약, 50만으로 가고자 하는데 0~5번까지만 망가져있다면 어떨까? 그렇다면 100번에서 50만으로 +버튼을 통해 이동하는 것은 499900번의 연타가 필요하지만, 666666에서 500000으로 오는 것은 166666번만 연타하면 된다.
즉, 이 문제는 0~50만까지의 숫자만이 아니라 더 넓게 잡아서 최대 0~100만까지의 채널 중 이동이 가능하다고 대략 이해하고 그 뒤 +/- 버튼을 통해 원하는 채널로 이동하는 경우 중 최소의 경우를 구하는 문제이다.
→ 엄밀히는 100만은 아니다. N이 주어질 때, Nx2-100 까지만 체크하면 되겠지만 사실상 시간복잡도로 볼 때 큰 차이가 없으니 대충 정해도 된다.
이 문제는 0~100만까지의 숫자로 이동해서 각 숫자의 자리수가 고장난 상태인지 아닌지를 체크해야 하니, 가능한 모든 숫자를 탐색하는 완전 탐색 방식으로 해결할 수 있다.
해결 과정은 다음과 같다.
① 0~Nx2까지의 범위 중 이동할 채널 C를 탐색한다.(혹은 100만까지 해도 됨)
② C번 채널의 각 자리수 중 고장난 버튼이 있는 지 탐색한다.(있으면 그 채널로 이동 불가)
→ 방법 1 : 문자열로 전환하여 각 문자에 대해 체크하기
→ 방법 2 : 10으로 나눈 나머지를 연속으로 체크하기
③ 고장난 버튼이 없다면 C채널로 이동하는데 누르는 0~9번 버튼의 수와 |N-C|를 통해 +/-를 누르는 수를 더한다.
④ 구해진 수 중 최소의 값을 정답으로 한다.
시간복잡도는 최대 100만에 각 자리수를 점검하는 경우의 수를 곱한 것인데, 숫자마다 자리수가 다르므로 계산이 쉽지 않다. 하지만 모든 숫자가 7자리라고 대략 가정하면 O(7,000,000)이 최대이므로 이 보다는 무조건 작다.
1초에 약 1억번의 연산이 가능한 컴퓨터의 입장에서 전혀 무리가 되는 복잡도가 아니다.
3. 코드
아래의 코드를 통해 정답을 알아보자.
import java.io.*;
public class Main{
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
int m = Integer.parseInt(br.readLine());
// 고장난 버튼 설정
boolean broken[] = new boolean[10];
// 이것이 없이 설정하면 Nullpointer 에러가 발생할 수 있으니 주의
// m==0일 때의 예외 처리를 해야함
if(m > 0){
String[] b = br.readLine().split(" ");
for(int i=0; i < b.length; i++){
int idx = Integer.parseInt(b[i]);
broken[idx] = true;
}
}
int ans = Math.abs(n - 100);
// 몇 번 클릭하는 것이 최소인지 확인
for(int i=0; i <= 1000000; i++){
if(m == 10) break;
int click = brute_force(broken, i);
if(click == -1) continue;
ans = Math.min(ans, click + Math.abs(n-i));
}
bw.write(String.valueOf(ans));
bw.flush();
br.close();
}
private static int brute_force(boolean[] broken, int i){
int temp = i;
int click = 0;
while(true){
// 누를 버튼 확인
int div = temp % 10;
// 고장난 버튼이면 -1 반환
if(broken[div]) break;
// 현재 값을 10으로 나누고, click 값은 1씩 더한다.
temp /= 10; click++;
// 나눈 뒤에도 0이면 반복문 탈출
if(temp == 0) return click;
}
return -1;
}
}
읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.
