[BOJ 1107] 리모콘 (Java)

BOJ 1107 리모콘

문제풀이

가장 처음 생각한 방법은 목표 채널에 가장 가까운 채널로 번호 버튼을 사용하여 이동하고 +, - 버튼으로 이동하여 이동하는 방식이다. 하지만 채널의 길이(자리수)에 따른 많은 예외상황을 모두 커버하지 못한 그리디한 방식이였다. 따라서 브루트포스 방식으로 모든 경우의 수를 수행하는 것이 이 문제를 푸는 적합한 방식이다.

구현코드

package BOJ;

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

public class B1107_리모컨 {

	static boolean[] broken;
	static int N, M, limit, ans;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		N = stoi(br.readLine());
		M = stoi(br.readLine());
		
		broken = new boolean[10];

		if(M > 0) { // 고장난 버튼이 있을 때만 입력받기
			st = new StringTokenizer(br.readLine()); 
		}
		
		for(int i = 0 ; i < M ; ++i) {
			broken[stoi(st.nextToken())] = true;
		}
		
		limit = ("" + N).length() + 1; // 채널의 최대 자릿수 
		ans = Math.abs(N - 100); // +, - 버튼만으로 이동하는 경우 
		
		for(int i = 0 ; i < 10 ; ++i) { // 입력채널 첫번째 자릿수 결정 
			if(!broken[i]) {
				click(1, i);
			}
		}
		
		System.out.println(ans);
	}

	private static void click(int length, int channel) {
		if(limit < length) {
			return;
		}
		
		int cur = Math.abs(N - channel) + length; // 현재 입력된 채널에서 목표 채널로 가기위한 횟수
		ans = ans > cur ? cur : ans;  // 최솟값 갱신 
		
		for(int i = 0 ; i < 10 ; ++i) {
			if(!broken[i]) {
				click(length + 1, (channel * 10) + i); // 스트링을 사용하지않고 10을 곱하고 더함으로써 해결 
			}
		}
	}

	private static int stoi(String s) {
		return Integer.parseInt(s);
	}
}

• 재귀함수의 매개변수를 넘길 때 길이 때문에 String을 사용해야한다고 생각했었는데 int 형을 사용하고 매번 10을 곱하고 새로운 수를 더해주는 방식으로 해결할 수 있었다.
• 최솟값을 갱신하는 부분이 항상 재귀함수 탈출 조건안에서 해야한다고 생각했는데 모든 경우의 수를 포함하기 위해서 탈출 조건 밖에 위치시켰다.