728x90
728x90

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

 

1107번: 리모컨

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

www.acmicpc.net

 

 

문제

수빈이는 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);

		
	}

}

 

 

 

 

 

 

728x90

+ Recent posts