[백준/Java] 1107 - 리모컨

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

문제

---

풀이

채널 N으로 가기 위한 방법을 비교해서 버튼을 최소로 누르는 횟수를 찾는 문제이다

 

방법 1: `(+, -)` 만 사용해서 N까지 가기

- 현재 채널 100에서 N까지 +, - 만 누른다

- 버튼 누르는 횟수: `abs(N - 100)`

 

방법 2: 숫자 버튼 + `(+, -)` 버튼 사용하기

- 고장나지 않은 버튼으로 N에 가까운 채널(C)을 누른다

- 누른 채널에서 +, - 버튼으로 나머지 거리를 이동한다

- 버튼 누르는 횟수: `C를 누르는 횟수 + abs(N - C)`

 

완전 탐색을 통해 0번 채널부터 N보다 충분히 큰 채널(약 1,000,000)까지 탐색한다

왜 1,000,000이냐면, N이 500,000이고 버튼 고장으로 500,000 이하의 수를 입력할 수 없다면 N보다 큰 수에서 내려와야 할 것이다. 1,000,000이라는 수는 모든 경우를 커버하기에 안전한 범위이다

 

자세한건 코드를 보자

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;


public class Main {

	static boolean[] broken = new boolean[10];

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();

		final int baseChannel = 100;

		int N = Integer.parseInt(br.readLine());
		int M = Integer.parseInt(br.readLine());

		if (M != 0) {
			st = new StringTokenizer(br.readLine());
			// 고장난 버튼은 true
			for (int i = 0; i < M; i++) {
				broken[Integer.parseInt(st.nextToken())] = true;
			}
		}


		// N까지 +, - 만 눌러서 갈 수 있는 경우를 기본으로 잡는다
		int answer = Math.abs(N - baseChannel);

		for (int i = 0; i <= 1000000; i++) {
			// 채널번호 i를 완전히 누를 수 있으면
			if (isPossible(i)) {
				// i를 누르는 횟수(i의 자릿수) + N까지 +,-로 가는 거리
				int cnt = String.valueOf(i).length() + Math.abs(N - i);
				answer = Math.min(answer, cnt); // 최솟값을 갱신
			}
		}


		System.out.println(answer);

		br.close();
	}

	static boolean isPossible(int channel) {
		// 채널 번호의 각 자릿수를 누를 수 있는지 확인
		String str = String.valueOf(channel);
		for (int i = 0; i < str.length(); i++) {
			// 고장난 버튼이 하나라도 있으면 false
			if (broken[Integer.parseInt(String.valueOf(str.charAt(i)))]) {
				return false;
			}
		}
		return true;
	}

}

결과