[백준] 1107번 - 리모컨

1107번 - 리모컨

---

<문제>

https://www.acmicpc.net/problem/1107

1107번: 리모컨

 

<문제 풀이>

처음 문제를 이해하고 접근할 때 완전 탐색 방법은 배제하고 접근을 했다. 

길이가 10인 배열에 고장 난 버튼은 1, 정상작동 버튼은 0으로 초기화했다. 

 위의 예제에서 답을 구하는 방법은 5455++, 5459-- 2가지 방법이 있다. 

7에서 1씩 증가, 1씩 감소 2가지 방향으로 리모컨 클릭수를 누적하였다. 

하지만 이 예제는 마지막 자릿수의 버튼만 고장인 상태라 간단해 보이지만 만약 5도 고장 난 버튼에 포함된다고 생각하면 경우의 수가 많아진다. 

그래서 시간제한도 2초이고, 브루트포스 알고리즘  문제인 것을 감안하여 완전 탐색으로 다시 접근했다. 

 

채널의 시작 위치가 100번이므로 버튼 누적수의 초기값을 |100 - N|으로 설정하고 구현을 시작한다. 

완전 탐색을 할 때 for문의 i 범위가 0 ~ 999,999인 것은 쉽게 알 수 있을 것이다. 

만약 i가 4549일 때와 4547일 때를 생각해 보자.

i = 4549 일 때, i 값에 고장 난 버튼이 없기에 해당 채널을 4번의 버튼을 눌러 찾을 수 있다. 그리고 N만큼의 차이만큼 +,-버튼으로 이동하여 버튼 누적 횟수를 알 수 있다. 

i = 4547 일 때, i 값에 고장 난 버튼(7)이 있기에 이 값은 고려하지 않고 다음 i 값으로 넘어간다. 

이렇게 고장 난 버튼이 포함되어 있을 경우 다음 값으로 넘기고, 고장 난 버튼이 포함되어 있지 않다면 N까지 도달할 수 있는 버튼의 누적 횟수를 저장한다. 

이때 저장된 버튼의 누적 횟수와 이전 값에 대해 저장된 누적 횟수 값을 비교해 최솟값을 최종적으로 저장한다. 

i = 999,999 일 때까지 반복하면 N번까지의 버튼 누적 횟수의 최솟값을 얻을 수 있다. 

 

추가적으로 

N이 100일 때와 M이 0일 때를 예외처리 해줬다.

(처음에 M이 0일 때를 예외처리 하지 않아 런타임에러를 엄청나게 봤다........)

 

<코드>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int N = Integer.parseInt(br.readLine());
		int M = Integer.parseInt(br.readLine());
		int[] btn = new int[10];
		int cnt = Math.abs(100-N); //count의 초기값 
		
		if(N == 100) {
			cnt = 0;
		}
		if(M != 0) { //NullPoint 방지
			st = new StringTokenizer(br.readLine()); 
			for(int i = 0; i < M; i++) {
				int input = Integer.parseInt(st.nextToken());
				btn[input] = 1;
			}
		}
		
		for(int i = 0; i <= 999999; i++) {
			String s = String.valueOf(i);
			int len = s.length();
			
			boolean flag = true;
			for(int j = 0; j < len; j++) {
				int idx = s.charAt(j) - '0';
				if(btn[idx] == 1) {
					flag = false;
					break;
				}
			}
			
			if(flag) {
				int minValue = Math.abs(N-i) + len;
				cnt = Math.min(cnt, minValue);
			}
		}
		System.out.println(cnt);
	}
}

 

<결과>

 

 

2023.04.06