https://www.acmicpc.net/problem/1107
문제
> 수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다.
리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다.
수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오.
수빈이가 지금 보고 있는 채널은 100번이다.접근
주어진 N이 최대 500,000까지니까 내가 누를 수 있는 수들 중 봐야하는 수는 0부터 최대 999,999번이다.
이때 고장난 번호까지 생각해서 번호의 각 자리마다 검증한다고 하면 최대 6자리이므로 1,000,000 x 6이므로 모든 수를 따져줬다.
문제해결
> 원하는 번호 N과 고장난 번호의 개수 M을 입력받는다.
> 고장난 번호를 boolean배열에 기록해 검증할 때 사용한다.
> 누르는 횟수의 최소번 수를 rst변수에 저장할 것이고 초기값은 처음 채널 100번에서 해당 번호까지 +/-로만 가는 경우를 준다.
> 이때 처음부터 100번에 있으면 0번 움직이므로 이를 처리해준다.
> 아니라면 고장난 번호를 보는데 고장난게 있을 때만 valid배열에 고장난 번호를 기록한다.
> 이제 0번부터 999,999번까지 돌며 해당 번호를 문자열로 변환해 각 자리마다 누를 수 있는 번호인지 검증한다.
> 누를 수 없다면 다음 번호로 넘어가준다.
> 검증을 통과해 누를 수 있는 번호라면 해당 번호에서 원하는 번호로 가는 횟수를 구한다.
> 해당 번호를 누르는 횟수인 자릿수 + 해당 번호 - 원하는 수의 절대값을 더해준다.
> 이 수를 rst와 최소값 연산을 하면서 최소값을 구한다.코드
import java.io.*;
import java.util.*;
import java.lang.*;
public class Main {
//1107번 리모컨
static int N, M;
static boolean[] valid = new boolean[10];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
M = Integer.parseInt(br.readLine());
Arrays.fill(valid, true);
int rst = Math.abs(N- 100); //100번에서 +,-로 왔다갔다 하는걸 초기값
if(rst == 0) { //시작부터 목표채널이면 0번 끝
System.out.print(rst);
System.exit(0);
}
if(M != 0) { //고장난 번호 있으면 입력받아 저장
StringTokenizer st = new StringTokenizer(br.readLine());
while(st.hasMoreTokens()) valid[Integer.parseInt(st.nextToken())] = false;
}
for(int i = 0; i < 1000000; i++) {
String n = i + "";
boolean invalid = false;
for(int j = 0; j < n.length(); j++) {
if(!valid[n.charAt(j) - '0']) {
invalid = true;
break;
}
}
if(invalid) continue;
rst = Math.min(rst, n.length() + Math.abs(N-i));}
System.out.print(rst);
}
}
후기
최대한 횟수를 줄이기 위해 원하는 번호를 만들기 위해 직접 누를 수 있는 번호는 누르는걸로 해보려고 했지만 예외가 많고 중간중간 처리가 불가능한 경우가 있었다. 그래서 전수조사 하는 방법으로 시간복잡도를 따져봤는데 가능해서 구현했는데 맞았다.
