백준 1107 리모컨 (Java)

1. 문제 링크

1107번: 리모컨

 

2. 문제 및 입출력예제

 

3. 문제 풀이

고장난 버튼을 boolean[] 배열에 담았다.

채널 변경은 +/- 버튼과 숫자 버튼을 이용해 이동할 수 있다.

고장나지 않은 버튼을 모두 눌러보면서 완전탐색을 진행했다.

 

채널 이동 범위를 설정하지 않으면 stackoverflow가 발생해서 추가했고

재귀 전에 검사하도록 해서 시간이 조금 많이 줄어들었다.

 

4. 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

	static int N, M, min, over;
	static boolean[] broken  = new boolean[10];
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		over = Integer.toString(N).length()+1;
		M = Integer.parseInt(br.readLine()); 
		if(M>0) {
			String[] split = br.readLine().split(" ");
			for(int i = 0;i<split.length;i++) {
				broken[Integer.parseInt(split[i])] = true;
			}
		}
		min = Math.abs(N-100);
		
		for(int i=0;i<10;i++) {
			if(broken[i]) {
				continue;
			}
			solve(1, i);
		}
		System.out.println(min);
	}
	private static void solve(int count, int channel) {
		min = Math.min(min, count+Math.abs(N-channel));
		for(int i=0;i<10;i++) {
			if(broken[i]) {
				continue;
			}
            if(over<count+1) { 
			    return;
		    }
			solve(count+1, channel*10 + i);
		}
	}
}