[Java] 백준 1107번 - 리모컨 (완전 탐색)

문제 링크 :  https://www.acmicpc.net/problem/1107

1107번: 리모컨

 

 

문제

수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다.

리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다.

수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오. 

수빈이가 지금 보고 있는 채널은 100번이다.

입력

첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다.  둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주어지며, 같은 버튼이 여러 번 주어지는 경우는 없다.

출력

첫째 줄에 채널 N으로 이동하기 위해 버튼을 최소 몇 번 눌러야 하는지를 출력한다.

 

 

---

 

접근 방법

 

간단해 보이지만 의외로 복잡한 문제였다.

 

누군가 친절하게 올려주신 반례를 사용해서 풀 수 있었다.

* 반례 모음(https://www.acmicpc.net/board/view/46120)

 

1555
8
0 1 3 4 5 6 7 9

 

를 예로 들어보자. 결론부터 말하면 답은 670이고 888을 누른 뒤(3번) 667번(1555-888) -버튼을 누를 때가 최소로 버튼을 눌러서 1555를 만드는 경우이다. 나는 아래의 방법으로 생각해서 틀렸다. 

 

 

처음에는 한 자리수씩 따져서 고장나지 않은 버튼으로 누를 수 있는 숫자를 만든 후 더 적게 +/-를 눌러서 N에 도달하는 경우일 때 해당 숫자를 저장했다.

즉, 1은 고장난 버튼이니 

case1) 2부터 9까지의 수 중에 고장나지 않은 버튼 중 최소 수를 구한다. -> 2

case2) 0부터 0까지 수 중에 고장나지 않은 버튼 중 최대 수를 구한다. -> 없음

 

2를 저장한다.

 

그 다음은 5인데, 5도 고장난 버튼이니

case1) 6부터 9까지의 수 중에 고장나지 않은 버튼 중 최소 수를 구한다. -> 8 -> 28 -15 = 13

case2) 4부터 0까지 수 중에 고장나지 않은 버튼 중 최대 수를 구한다. -> 2 -> 22 - 15 = 7

 

13>7로 더 작은 case2) 의 2를 앞에서 저장한 2 뒤에 붙여 22를 저장한다. 

 

그래서 결국 2222를 만든 후(2버튼 4번 누름) 667번(2222-1555)을 -버튼을 눌러서 1555를 만들 수 있다. 이 때 답은 4+667 = 671이 된다. 

 

 

 

결국 완전 탐색으로 풀어주었다. i = 0부터 999999까지 돌면서 (N의 최대값이 500,000이므로 6자리수 중 최대 값까지 검사한다) 검사한다.

만약 고장난 버튼 때문에 i를 바로 누르지 못하면 다음 수를 검사한다.

아니라면 i의 자리수 + |N-i| 를 구하며 이 값의 최소값을 저장한다.

 

 

import java.util.*;

public class BF_BOJ1107_리모컨 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		int N, M;
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		
		ArrayList<Integer> troubleButton = new ArrayList<Integer>();
		
		
		for(int i = 0; i<M; i++) {	//고장난 버튼 
			int but = sc.nextInt();
			troubleButton.add(but);
		
		}
		
		int ans = Math.abs(100-N);			//+, - 버튼으로만 움직였을 때 
		
		int mini = 987654321;
		int cnt = 0;
		
		for(int i = 0; i<=999999; i++) {		//완전 탐색 
			
			String str = String.valueOf(i);
			boolean chk = true;
			for(int k = 0; k<str.length(); k++) {
				if(troubleButton.contains(str.charAt(k)-'0')) {		//고장난 버튼 때문에 바로 i 못 누르면 스킵 
					chk=false; break;
				}
			}
			if(chk==false) continue;
			
			cnt = str.length() + Math.abs(i-N);	//고장난 버튼 없어서 바로 i를 누를 수 있으면 i 누르고 +/- 눌러서 이동  
			
			
			if(cnt < mini) {
				mini = cnt;
			}
	
		}
		
		if(mini < ans) ans = mini;
		System.out.println(ans);

		
	}

}