[BaekJoon] 1107 리모컨

1.  문제 링크

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

2.  문제

요약

• 버튼이 0부터 9까지의 숫자와 +, -가 있는 리모컨이 있는데 일부 숫자 버튼이 고장났습니다.
• +를 누르면 현재 보고 있는 채널에서 +1된 채널로 이동하고 -를 누르면 -1된 채널로 이동하며 채널 0에서 -를 누른 경우는 채널이 변하지 않고 채널은 무한대만큼 있습니다.
• 현재 100번 채널에 위치해있고 이동하려고 하는 채널 N과 어떤 버튼이 고장났는지 주어질 때, 채널 N으로 이동하기 위해 버튼을 최소로 몇 번 눌러야 하는지 구하는 문제입니다.
• 입력: 첫 번째 줄에 0보다 크거나 같고 500,000보다 작거나 같은 N이 주어지고 두 번째 줄에 0보다 크거나 같고 10보다 작거나 같은 고장난 버튼의 개수 M이 주어지며 고장난 버튼이 있을 경우 세 번째 줄에 고장난 버튼들이 주어집니다.
• 출력: 첫 번째 줄에 채널 N으로 이동하기 위해 버튼을 최소 몇 번 눌러야 하는지 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
	public int getMinNum(int channel, boolean[] broken) {
		int min = Math.abs(channel - 100);
		for(int i = 0; i <= 999999; i++) {
			String num = String.valueOf(i);
			int len = num.length();
			boolean isBreak = false;
			for(int j = 0; j < len; j++) {
				if(broken[num.charAt(j) - '0']) {
					isBreak = true;
					break;
				}
			}
			if(!isBreak) {
				int count = Math.abs(channel - i) + len;
				min = Math.min(min, count);
			}
		}
		return min;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int channel = Integer.parseInt(br.readLine());
		int num = Integer.parseInt(br.readLine());
		boolean[] broken = new boolean[10];
		if(num != 0) {			
			String[] input = br.readLine().split(" ");
			br.close();
			for(int i = 0; i < num; i++) {
				broken[Integer.parseInt(input[i])] = true;
			}
		}
		Main m = new Main();
		bw.write(m.getMinNum(channel, broken) + "\n");
		bw.flush();
		bw.close();
	}
}

4.  접근

• 해당 문제는 완전탐색을 이용하여 해결합니다.
• 해당 채널로 이동하는 방법은 +, - 버튼을 이용하여 해당 채널까지 가는 방법과 해당 채널 혹은 근처 채널로 숫자들을 눌러서 이동한 후 +, -로 이동하는 방법이 있습니다.
• 두 방법 중 더 적게 누르는 방법을 이용하여 최소로 버튼을 누르는 횟수를 구합니다.
• 문제에서 이동하려는 채널의 최댓값이 500,000이라고 하였으므로 탐색을 진행할 때, 0번 채널부터 999,999번 채널까지 탐색을 진행합니다.
  • 만약 9를 제외한 모든 버튼들이 고장난 상황이라면, 999,999번 채널로 이동한 후에 - 버튼을 이용하여 이동해야하므로 탐색할 채널의 최댓값을 999,999번으로 합니다.

1. 고장난 숫자 버튼을 표시하기 위한 boolean 타입의 1차원 배열 broken을 생성하고 고장난 버튼에 해당하는 위치를 true 값으로 설정합니다.
2. 우선 +/- 버튼만을 이용하여 이동하는 경우에서의 버튼을 누르는 횟수를 변수 min에 설정합니다.
3. 0번 채널부터 999,999번 채널까지 탐색하면서 각 채널로 숫자 버튼을 이용해 이동한 후에 +/- 버튼을 이용하여 이동하려는 채널까지 이동하는 경우에서의 버튼을 누르는 횟수를 구하고 모든 경우에서 가장 적게 버튼을 누르는 횟수를 구합니다.
   1. 각 채널로 숫자 버튼을 이용해 이동할 때 버튼을 누르는 횟수를 변수 len에 설정합니다.
   2. 각 채널에 있는 숫자들에 고장난 버튼에 해당하는 숫자가 있는지 나타내는 isBreak라는 변수를 생성하고 false로 초기화합니다.
   3. 각 채널의 각 숫자들을 앞에서부터 확인하면서 고장난 버튼에 해당하는 숫자인지 확인합니다.
   4. 만약 고장난 버튼에 해당하는 숫자가 없다면 각 채널에서 +/- 버튼을 이용하여 원하는 채널까지 이동할 때에 버튼을 누르는 횟수와 변수 len의 값을 더하여 count 변수에 설정합니다.
   5. 변수 count의 값과 변수 min의 값 중 더 작은 값을 min 변수에 설정합니다.
4. 3번 반복문이 끝난 후에 변수 min의 값을 출력합니다.