[BOJ-1107] 리모컨(JAVA)

[BOJ-1107] 리모컨(JAVA)

728x90

백 준 1107 리모컨

문제 설명

- 수빈이는 리모컨을 이용하여 TV 채널을 돌리려고 한다.

- 리모컨은 0부터 9까지 숫자와 +, - 버튼이 있다.

- 수빈이가 이동려는 채널은 N이다.

- 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야 하는지 구하라.

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

입력 값

- 첫째 줄에 수빈이가 이동려고 하는 채널 N이 주어진다.

( 0 <= N <= 500,000 )

- 둘째 줄에는 고장난 버튼의 개수 M이 주어진다.

( 0 <= M <= 10 )

- 고장난 버튼이 있는 경우에는 셋째 줄에 고장난 버튼이 주어진다.

( 같은 버튼이 여러 번 주어지는 경우는 없다. )

예제

문제 분석

- 수빈이가 이동하려는 채널은 최소 0에서 최대 50만이다.

그리고, 이동을 위한 버튼은 최소로 눌러야 하기 때문에 숫자를 이용하여 만들 수 있는 값은 100만 미만이다.

- 왜냐하면, 100에서 50만을 만들기 위해서는 +버튼을 49만9900번을 눌러야 한다.

즉, 이것과 같은 숫자로 50만을 만들기 위해서는 숫자 버튼 998994를 누르고, -를 49만8994번 누르면 된다.

998994보다 큰 숫자를 누르면, 반드시 100에서 시작하는 숫자보다 커지게 된다.

- 즉, 모든 숫자는 길어야 6자리의 숫자이라는 것이다.

- 각 숫자는 0~9를 가질 수 있기 떄문에, 최대 6자리의 숫자를 만들 수 있는 경우의 수는 $10^6$ = 1,000,000 이다.

- 해당 숫자를 만들고, (해당 숫자-100)을 하면 몇 번으로 +, - 버튼을 눌러야 하는지 알 수 있다.

- 그러므로 해당 숫자를 만들고, 해당 숫자에서 N까지 +, - 버튼을 몇 번 눌러야 하는지 판단하면 된다.

- 결론적으로, 0~9를 이용하여 6자리 숫자를 만들 수 있는 모든 경우를 살펴보고,

해당 숫자에서 N을 만들기 위해 +, - 버튼을 몇 번 누르는지 계속해서 최소 값을 찾아 갱신하면 된다.

소스 코드

import java.io.BufferedReader; import java.io.FileInputStream; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static int result=Integer.MAX_VALUE; public static int N,M; public static int NSize; public static void main(String[] args) throws IOException { BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); N = Integer.parseInt(bf.readLine()); M = Integer.parseInt(bf.readLine()); NSize = String.valueOf(N).length(); boolean numbers[] = new boolean[11]; if(M>0){ StringTokenizer st =new StringTokenizer(bf.readLine()); for(int i=0;i 6){ return; } if(nowNumber.length()>0){ int nowN = Integer.parseInt(nowNumber.toString()); int nowSize = String.valueOf(nowN).length(); result = Integer.min(Math.abs(N-Integer.parseInt(nowNumber.toString()))+nowSize,result); } for(int i=0;i<=9;i++){ if(!numbers[i]){ nowNumber.append(i); findNum(numbers,nowNumber); nowNumber.setLength(nowNumber.length()-1); } } } }

from http://9327144.tistory.com/97 by ccl(A) rewrite - 2021-09-26 22:01:21