• 백준 1107번 리모컨 [브루트 포스] :: 마이구미
    알고리즘 풀이/브루트 포스 2017. 5. 10. 23:12
    반응형

    이번 글은 백준 알고리즘 문제 1107번 "리모컨" 을 다뤄본다.

    문제 접근 방법은 브루트 포스. 즉, 노가다로 해결할 수 있다.

    1107번 리모컨 - https://www.acmicpc.net/problem/1107


    리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다.

    수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 망가져있는지 주어졌을 때, N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오. 

    수빈이가 지금 보고 있는 채널은 100번이다.


    본인은 처음에 단순히 채널을 한자리씩 분해하여 목표 채널에 가깝게 가는 방식으로 접근했다.

    하지만 이 경우 반례가 너무 많이 존재한다. (문제를 풀어봤다면 이해하리라 생각한다)


    그래서 생각한 방법이 브루트 포스이다.

    사실상 테스트 케이스도 500,000 이기 때문에 충분히 가능하다.


    문제에서 목표 채널로 이동하기 위한 방법은 3가지로 분류할 수 있다.

    1. 자 버튼을 통해 목표 채널에 도달한다.
    2. 숫자 버튼을 통해 가까운 채널로 이동한 후, + 또는 - 버튼을 통해 목표 채널에 도달한다.
    3. + 또는 - 버튼을 통해 목표 채널에 도달한다.

    본인이 구현한 방법은 단순히 0~88888 각 채널이 목표 채널로 이동할 수 있는 횟수를 구하면서 최소를 뽑아낸다.

    테스트 케이스는 500000이지만, 채널을 500000 이상으로 이동한 다음 - 버튼을 이용할 수 있는 경우도 있다.

    대표적인 입력 예는 아래와 같다.


    500000

    8

    0 1 2 3 4 5 6 7


    본인의 구현 방큰 틀은 아래와 같다.


    1. 언급한 이동할 수 있는 방법 3번을 기준.


    int ans = Math.abs(n - 100); // + 또는 - 버튼으로만 이동 횟수를 기준.


    2. 숫자 버튼을 통해 이동할 수 있는 채널인지 확인.


    for (int i = 0; i <= 888888; i++) { // i는 번호 버튼을 눌러 가까운 번호로 이동으로 가정. boolean flag = false; String current = String.valueOf(i); int len = current.length(); for (int j = 0; j < len; j++) { int value = current.charAt(j) - '0'; if (!check(remocon, value)) { flag = true; break; } }

    // 아래 3번

    ............ }


    3. 숫자 버튼을 통해 이동할 수 있을 경우 


    if (!flag) { // 숫자 버튼 횟수 + 이동한 번호와 목표 번호간의 차이 if (ans > Math.abs(i - n) + len) { ans = Math.abs(i - n) + len; } }


    전체 소스를 보면 더욱 이해가 빠를 거라 생각한다.

    소스는 아래 Github URL을 참고하길 바란다.


    백준 알고리즘 1107번 리모컨 전체 소스

    https://github.com/hotehrud/acmicpc/blob/master/algorithm/Brute-Force/1107.java




    반응형

    댓글 0

Designed by Tistory.