백준_1107 리모컨 (자바) / 브루트포스

시간 & 메모리 제한

문제

입력 & 출력

브루트포스를 이용한 문제풀이

package com.Back;

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

public class Back_1107 {
	static int G,N,ans;
	static boolean[] broken;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		G = Integer.parseInt(br.readLine());
		N = Integer.parseInt(br.readLine());
		broken = new boolean[10];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			int temp = Integer.parseInt(st.nextToken());
			broken[temp] = true;
		}
		
		ans = Math.abs(G-100);
		
		for (int i = 0; i < 1000000; i++) {
			int len = chk(i);
			
			if(len !=0) {
				int cnt = Math.abs(i-G);
				if(ans>len+cnt) {
					ans = len+cnt;
				}
			}
		}
		System.out.println(ans);
	}
	private static int chk(int i) {
		
		if(i==0) {
			if(broken[0]) {				
				return 0;
			}
			else {				
				return 1;
			}
		}
		
		int len = 0;
		while(i>0) {
			if(broken[i%10]) {
				return 0;
			}
			len++;
			i /=10;
		}	
		return len;
	}
}

- Step 1. boolean을 이용해서 망가진 번호를 true로 바꿔 준다.

 

- Step 2. for문을 통해서 1000000개를 돌려준다. 0부터 50만까지 올라갈수도 있지만, 반대로 50만부터 0으로 내려올수도 있기 때문에 모두 조사를 해준다.

 

- Step 3. chk를 이용해서 i에 대해서 위, 아래 버튼이 아닌 번호 버튼을 이용해서 누를 수 있는지를 판단하는 버튼이다.

 

- Step 4. len이 0인 경우는 ans보다 커지기 때문에 넘어가고, 0보다 큰 경우에 대해서만 계산을 해준다. 

 

예를 들어 풀어서 보면

 

5457

3

6 7 8

의 경우에 처음 ans 값은 5357이 될 것이다.

 

i의 값이 5450쯤 돌때를 보면 chk를 돌려보면 4개 모두 broken에 해당하지 않기 때문에 4가 된다

 

cnt는 5450-5457 의 절댓값 7이 될것이다. 5450에서 7번만 누르면 5457이 되기 때문이다.

 

ans의 후보로 len은 4번  cnt는 7번 그래서 총 11번이 된다.

 

당연 5357은 아니겠지만, 11번이라는 숫자가 작다면 바뀌게 될것이다.

 

답은 5455일때 2번을 누르는 경우이다.

 

5455가 i일때 len은 4가 되고 cnt는 2가 된다. 그래서 총 6번이 된다.