[Gold V][JAVA]1107:리모컨

1107번:리모컨

문제 유형: 완전탐색 : 브루트포스 알고리즘 Brute Force Algorithm

Brute : 무식한
Force : 힘

완전 탐색이라는 이름에서도 알 수 있듯이 하나부터 열까지 모든 경우를 다 탐색하는 알고리즘이다.

접근 방식 및 풀이

• 완전탐색 알고리즘을 사용하여 모든 케이스들을 생각해내야 한다.
• 조건 1. 100이면 count 0
• 조건 2. 리모콘이 고장 나지 않았으면, 배열의 숫자만큼 또는 리모컨 +- 한 count 중 최소값
• 조건 3. 리모콘이 고장 났으면,  고장난 리모컨으로 누를수 있는 숫자 케이스와 리모컨 +- 한 count 중 최소값

예를 들어, 예제 입력 1의 경우를 살펴보겠습니다:

N = 5457
M = 3
고장난 버튼: 6, 7, 8

• 초기값 설정: ans = Math.abs(N - 100)으로 초기화됩니다. 즉, 초기값은 현재 채널 100에서 N까지의 거리입니다.

• 이동하려고 하는 채널이 0부터 50만까지이다. 밑에서부터 위로 50만까지 갈 수도 있지만, 위에서부터 밑으로 50만까지 갈 수 있으므로 0부터 100만까지의 모든 숫자를 확인한다. for(int i = 0; i <= 1000000; i++)

dfs()

• 예제 입력 1에서는 고장난 버튼이 6, 7, 8이므로 이를 고려하여 채널을 탐색합니다.
• 탐색 중인 채널이 5455인 경우를 생각해보겠습니다. 이 채널은 고장난 버튼이 없으므로 사용 가능한 채널입니다. 이동한 횟수와 채널 번호의 길이를 더하여 이동에 필요한 총 버튼 클릭 횟수를 계산합니다. 즉, min = Math.abs(N - i) + len을 계산합니다.
• 현재 채널과 이동하려는 채널의 거리: Math.abs(5457 - 5455) = 2
• 채널 번호의 길이: len = 4 (채널 번호의 길이가 4자리이므로)
• 따라서 이동에 필요한 총 버튼 클릭 횟수: 2 + 4 = 6
• 이렇게 계산된 버튼 클릭 횟수를 이전에 계산된 최소값과 비교하여 작은 값으로 업데이트합니다.
• 모든 가능한 채널에 대해 이와 같은 과정을 반복합니다.
• 최종적으로 ans 변수에는 총 버튼 클릭 횟수가 저장되어 있고, 이 값을 출력합니다.

이렇게 하면 고장난 버튼이 없는 채널로 이동하기 위해 필요한 최소 버튼 클릭 횟수가 출력됩니다.

정답

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

public class Main {  //문제유형: 브루트포스 , 메모리 제한: 256MB, 시간 제한: 2초s
    static boolean[] chk;
    static int ans, N, M;

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

        N = Integer.parseInt(br.readLine()); //채널
        M = Integer.parseInt(br.readLine()); //고장난 버튼 수


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

        ans = Math.abs(N - 100); // 100부터 +, -를 이용해서 움직이는 경우

        dfs(); //버튼 누른 후 움직이는 경우
        System.out.println(ans);
    }

    public static void dfs() {
        for (int i = 0; i <= 1000000; i++) { //이동하려고 하는 채널이 0부터 50만(밑, 위 고려)
            String str = String.valueOf(i);
            int len = str.length();

            boolean up = false;
            for (int j = 0; j < len; j++) {
                if (chk[str.charAt(j) - '0']) { //고장난 번호가 리스트에 있는지 확인
                    up = true;
                    break;
                }
            }

            if (!up) {
                int min = Math.abs(N - i) + len; //(현재 탐색 중인 채널과 이동하려는 채널 차이) + 채널 길이
                ans = Math.min(min, ans);
            }
        }
    }
}