[백준] 1107번 - 리모컨(Java)

풀이

키워드

• 브루트포스

  정해진 규칙이 딱히 없으니, 브루트포스로 일일이 다 해봐야 한다는 것을 알 수 있다. 그런데 이 때 어떤 것을 일일이 다 해볼지가 문제이다. 브루토프스의 경우, 가장 큰 틀에서 경우의 수를 일일이 해보는 것부터 생각을 해봐야 한다. 이번 문제의 경우, N의 채널은 0 ~ 500,000까지 존재하므로 만약 모든 채널을 일일이 다 해본다면 50만 번의 시도가 필요하다. 즉 나쁘지 않은 시도횟수이므로 이것을 기준으로 브투르포스를 진행하면 되는 것이다.

  다만, 채널을 돌릴 때, 아래에서 N까지 시도해볼 수도 있고, 위에서 N까지 시도해볼 수도 있다. 예를 들어, N = 500000 일 경우 480000부터 시도해볼 수도 있지만, 520000부터 시도해볼 수도 있는 것이다. 어느 쪽에서 시도하는 것이 바람직한지는 고장난 번호에 따라 다를 것이다. 따라서, 우리는 0 부터 50만까지가 아니라, 0부터 100만까지의 경우의 수를 시도해봐야 한다. 여전히 나쁘지 않은 시도횟수이다.

  0부터 100만까지의 수 중 현재 시도해보는 수를 K라고 할 경우, K에 고장난 번호가 속해있는지를 알아야 한다. 만약 고장난 번호가 속해있으면, 이는 정답 후보군이 될 수 없다. 그리고 이 번호가 속해있는지 알기 위해서는 K의 각 자리 수를 뽑을 줄 알아야 한다. 이는 % 와 /=로 가능하다.

  예를 들어, 123456 이 있다면

• 123456 % 10 = 6    //1의 자리인 6 뽑기
• 123456 / 10 = 12345 
• 12345 % 10 = 5     / 5뽑기

  이런 방식을 되풀이하면 숫자 하나하나를 뽑아볼 수 있다. 또한, 숫자를 뽑으면서 뽑은 횟수도 세줘야 한다. 왜냐하면 (숫자를 뽑은 횟수) = (자릿이

키워드

브루트포스

  정해진 규칙이 딱히 없으니, 브루트포스로 일일이 다 해봐야 한다는 것을 알 수 있다. 그런데 이 때 어떤 것을 일일이 다 해볼지가 문제이다. 브루토프스의 경우, 가장 큰 틀에서 경우의 수를 일일이 해보는 것부터 생각을 해봐야 한다. 이번 문제의 경우, N의 채널은 0 ~ 500,000까지 존재하므로 만약 모든 채널을 일일이 다 해본다면 50만 번의 시도가 필요하다. 즉 나쁘지 않은 시도횟수이므로 이것을 기준으로 브투르포스를 진행하면 되는 것이다.

 

  다만, 채널을 돌릴 때, 아래에서 N까지 시도해볼 수도 있고, 위에서 N까지 시도해볼 수도 있다. 예를 들어, N = 500000 일 경우 480000부터 시도해볼 수도 있지만, 520000부터 시도해볼 수도 있는 것이다. 어느 쪽에서 시도하는 것이 바람직한지는 고장난 번호에 따라 다를 것이다. 따라서, 우리는 0 부터 50만까지가 아니라, 0부터 100만까지의 경우의 수를 시도해봐야 한다. 여전히 나쁘지 않은 시도횟수이다.

 

  0부터 100만까지의 수 중 현재 시도해보는 수를 K라고 할 경우, K에 고장난 번호가 속해있는지를 알아야 한다. 만약 고장난 번호가 속해있으면, 이는 정답 후보군이 될 수 없다. 그리고 이 번호가 속해있는지 알기 위해서는 K의 각 자리 수를 뽑을 줄 알아야 한다. 이는 % 와 /=로 가능하다.

 

  예를 들어, 123456 이 있다면

 

• 123456 % 10 = 6 //1의 자리인 6 뽑기
• 123456 / 10 = 12345 
• 12345 % 10 = 5 / 5뽑기

  이런 방식을 되풀이하면 숫자 하나하나를 뽑아볼 수 있다. 또한, 숫자를 뽑으면서 뽑은 횟수도 세줘야 한다. 왜냐하면 (숫자를 뽑은 횟수) = (자릿값의 개수) 이기 때문이다. 이 때 (자릿값의 개수) = (리모컨에서 "번호" 부분을 누르는 횟수) 라고 할 수 있다. 이 자릿값의 개수를 기억했다가, 이후 (N과 K의 차)에 이 (자릿값의 개수)를 더하면 총 누르는 리모컨의 버튼 횟수를 구할 수 있다.

 

 

---

코드

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

public class Main {
	static String N;
	static int M;
	static boolean [] arr;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = br.readLine();
		M = Integer.parseInt(br.readLine());
		arr = new boolean[11];
		if (M > 0) {
			String [] inputs = br.readLine().split(" ");
			for (int i = 0; i < M; i++) {
				arr[Integer.parseInt(inputs[i])] = true;
			}
		}
		
		int ans = Math.abs(Integer.parseInt(N) - 100);
		for (int i = 0; i < 1000001; i++) {
			int cnt = check(i);
			if (cnt != 0)
				ans = Math.min(ans, Math.abs(Integer.parseInt(N) - i) + check(i));
		}
		System.out.print(ans);
	}
	
	public static int check(int n) {
		if (n == 0) {
			if (arr[n])
				return 0;
			else
				return 1;
		}
		
		int cnt = 0;
		while (n > 0) {
			if (arr[n % 10])
				return 0;
			cnt++;
			n /= 10;
		}
	
		return cnt;
	}
}

 

배운점

1. 브루트포스의 경우, 가장 큰 틀에서의 경우의 수부터 고려해보기

2. 정수의 각 자릿수 뽑기 => %, /= 이용

---

출처 : www.acmicpc.net/problem/1107

1107번: 리모컨