솜이의 데브로그

백준 1107번 ) 리모컨 (java) 본문

Algorithm/백준

백준 1107번 ) 리모컨 (java)

somsoming 2022. 8. 1. 02:56

https://www.acmicpc.net/problem/1107

 

1107번: 리모컨

첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다.  둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼

www.acmicpc.net

 

문제

풀이

완전탐색 문제로, 채널의 최대값을 설정하고 모두 다 검색해보면서 고장나지 않은 번호들로부터 얼마나 이동해야하는지 최소 회수를 비교한다.

비교는 Math.abs와 Math.min 함수를 이용한다.

 

코드

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

public class BOJ_1107 {
    static boolean[] broken;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());
        broken = new boolean[10];

        if (M != 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int i = 0; i < M; i++) {
                int num = Integer.parseInt(st.nextToken());
                broken[num] = true;
            }
        }

        int min_cnt = Math.abs(N - 100);    // +,- 로만 누르는 경우
        for (int i = 0; i <= 1000000; i++) {
            int len = check(i);   // 숫자버튼 누르는 횟수
            if (len > 0) {
                int press = Math.abs(N - i);  // +,- 버튼 누르는 횟수
                min_cnt = Math.min(min_cnt, len + press);   // 최소 이동 횟수 계산
            }
        }

        bw.write(min_cnt + "\n");

        br.close();
        bw.flush();
        bw.close();
    }

    static int check(int n) {
        if (n == 0) {
            if (broken[0]) {
                return 0;
            } else {
                return 1;
            }
        }
        int len = 0;
        while (n > 0) {
            if (broken[n % 10]) {   // 고장난 버튼이 있는 경우
                return 0;
            }
            n /= 10;
            len += 1;   // 숫자버튼 누르는 횟수 증가
        }
        return len;
    }
}

'Algorithm > 백준' 카테고리의 다른 글

백준 2448번 ) 별 찍기 11 (java)  (0) 2022.08.01
백준 1253번 ) 좋다 (java)  (0) 2022.08.01
백준 2293번 ) 동전 1 (java)  (0) 2022.07.23
백준 10026번 ) 적록색약 (java)  (0) 2022.07.23
백준 12931번 ) 두 배 더하기 (java)  (0) 2022.07.22