백준 1107 / 리모컨

문제

풀이

설명

'리모컨을 이용해 원하는 채널을 바꾸려면 몇번 리모컨 버튼을 눌러야 하는가'를 구하는 문제이다.
즉, 리모컨 버튼을 누르는 최솟값을 구하는 문제

조건
• 버튼: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, ‒
• 일부 숫자 버튼이 고장났다.
• 현재 보고 있는 채널: 100
• 이동하려고 하는 채널: N(0 <= N <= 500000)
• 숫자 버튼을 눌러서 이동하는 채널C도 0<=C<=5000000 이면 된다.
• 최솟값을 구하는 문제이므로 채널 중복이 허용되지 않는다

따라서, 숫자 버튼을 누르고, 그 다음 +나 -중 하나만 연속으로 눌러야 한다.

이제 조건을 파악했으니 문제를 풀어보자

1. 이동할 채널 C를 정한다.
2. C에 포함되어있는 숫자 중에 고장난 버튼이 있는지 확인한다.

• 수를 문자열로 바꾼 다음, 한 글자씩 검사하는 방법
• 수를 10으로 계속해서 나누면서 하나씩 검사하는 방법

3. 고장난 버튼이 포함되어 있지 않다면 [C - N]을 계산해 +나 - 버튼을 몇번 눌러야 하는지를 계산한다.

코드

import java.util.Scanner;

public class Num1107 {
	
	static boolean[] broken = new boolean[10];
	static int possible(int c) {
		if (c == 0) {
			if (broken[0]) {
				return 0;
			} else {
				return 1;
			}
		}
		
		int len = 0;
		
		while (c > 0) {
			if (broken[c%10]) {
				return 0;
			}
			len +=1;
			c /= 10;
		}
		return len;
	}
	

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int M = sc.nextInt();
		
		for (int i = 0; i< M; i++) {
			int x = sc.nextInt();
			broken[x] = true;
		}
		
		int ans =  N -100;
		if (ans < 0) {
			ans = -ans;
		}
		
		// 이동할 채널 C를 정한다.
		for (int i = 0; i<= 1000000; i++) {
			
			int c = i;
			int len = possible(c);
			
			
			if (len> 0) {
				int press = c - N;
				
				if(press < 0) {
					press = -press;
				}
				if (ans > len + press) {
					ans = len + press;
				}
			}
			
		}
		
		System.out.println(ans);
		
	}
}

코드설명

참고 :
출처 : https://www.acmicpc.net/problem/1107