[백준] 1107번 : 리모컨 (java)

1107번: 리모컨 (acmicpc.net)

1107번: 리모컨

어떻게 생각하고 문제를 풀었는가?

N을 만드는 최소 값을 구하기 위해서 모든 경우의 수를 조사하는 Brute Force 방식을 사용하고자 하였습니다.

각 케이스에 해당하는 숫자가 에러 버튼을 눌러야 하는 경우를 제외하고 남은 케이스 중 눌러야 하는 버튼의 숫자가 가장 작은 값을 반환한다면 정답을 얻을 수 있을 것이라 생각하였습니다.

 

코드

import java.io.*;
import java.util.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Solution sol = new Solution();
        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());
        boolean[] error = new boolean[10];
        if(M>0){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int i=0; i<M; i++){
                error[Integer.parseInt(st.nextToken())] = true;
            }
        }
        System.out.println(sol.solution(N,error));
        br.close();
    }
}
class Solution{
    boolean[] error;
    public int solution(int N, boolean[] errArr){
        if(N==100) return 0;
        this.error = errArr;
        int answer = Math.abs(N-100);
        for(int i=0; i<1000001; i++){
            String str = String.valueOf(i);
            if(isValid(str)) answer = Math.min(Math.abs(N-i)+str.length(),answer);
        }
        return answer;
    }
    public boolean isValid(String str){
        for(int j=0; j<str.length(); j++){
            if(error[str.charAt(j)-'0'])   return false;
        }
        return true;
    }
}

Brute Force를 사용하여 정답을 찾는 코드입니다.

숫자 버튼은 0부터 9까지 존재하므로 크기가 10인 boolean 배열을 선언하여 어떤 숫자가 고장났는지 체크하고, 각 케이스의 문자열에 포함되지 않는다면 버튼의 수를 문자열의 길이 + |N-i|로 계산하여 최소 값을 저장합니다.

체널은 0부터 무한대만큼 존재하므로 N의 최대값인 500,000일때 0에서부터 1,000,000까지 경우의 수를 비교하여야 합니다.