[백준 1107번] 리모컨 - java

문제 설명

1. 현재 채널은 100에 있다.

2. 도착하고 싶은 채널과, 고장난 숫자들이 주어진다.

3. 위, 아래, 고장나지 않은 숫자들을 이용해 현재 위치에서 원하는 채널로 갈 때에 필요한 클릭 수를 구하면 된다.

풀이 과정

 1. 완전탐색을 통해 해결 가능하다.

 2. 현재 고장난 버튼들을 모두 기억한다.

 3. 도착하고 싶은 채널의 최대숫자는 500000이기 때문에, 0~1000000까지의 모든 채널로부터 해당 채널에 도착하는 경우를 구한다.

 4. 그리고 그 0~1000000의 채널에 대해 그 채널로 이동할 수 있는 경우(고장난 숫자가 없음)는 이동 후 +나 -를 통해 이동하면 된다.(차이의 절대값)

 예를 들어 도착하고 싶은 채널이 1517, 고장난 숫자가 1, 4, 6로 주어진 경우

 

0번 채널 -> 숫자를 통해 0번 채널로 이동 가능(숫자 1회 클릭) -> 0번 채널로부터 +버튼을 통해 1517로 이동하기(+버튼 1517회 클릭)  => 총 1518회 클릭함

1번 채널 -> 숫자를 통해 1번 채널로 이동 불가(1은 고장) -> 구할 필요 x

................

2000 채널 -> 숫자를 통해 2000채널로 이동 가능(숫자 4회 클릭) -> 2000채널로부터 -버튼을 통해 1517로 이동하기(-버튼 483회 클릭)  => 총 487회 클릭함

...............

이 경우 최소값을 계속해서 구하면 487회가 최소임을 알 수 있다.

 

 5. 그리고, 시작점이 100이라는 것을 알아야 한다. 예를 들어 102번 채널로 이동하고 싶은 경우, 따로 뭐 건드릴 필요 없이 +버튼을 두 번 클릭하면 된다. 따라서 처음에 원하는 채널을 입력받았을 때에 시작점 100채널로부터 해당 채널로 이동하는 경우를 먼저 구해서 넣어주면 된다.

코드

	import java.util.*;
	public class Main {
	public static boolean button[] = new boolean[10];
	public static int channer;
	public static void main(String args[]) {
	Scanner sc = new Scanner(System.in);
	channer = sc.nextInt();
	int N = sc.nextInt();
	for(int i=0; i<N; i++) button[sc.nextInt()] = true;
	int ans = Math.abs(channer-100); // +/-버튼만을 이용하여 원하는 채널로 이동하는 방법
	for(int i=0; i<=999999; i++){ // 0번 채널로부터 999999채널로 시작점을 설정한다.
	String nowChanner = i+""; // 현재 채널
	boolean can = true; // 현재 채널을 만들 수 있나?(고장난 숫자버튼이 없는가?)
	for(int j=0; j<nowChanner.length(); j++){ // 현재 채널의 모든 숫자들에 대해
	int nowButton = nowChanner.charAt(j) - '0'; // 현재 채널을 이루는 숫자
	if(button[nowButton]){ // 지금 숫자가 고장났다 -> 갈 수 없다.
	can = false;
	break;
	}
	}
	if(can){ // can이 true라면, 숫자를 통해 현재 i값, 즉 현재 채널로 갈 수 있다는 것이다.
	int click = nowChanner.length() + Math.abs(channer-i); // 클릭 수 = 현재채널로 갈 때 클릭한 숫자수 + 현재채널로부터 원하는채널로 이동하는 횟수
	ans = Math.min(ans, click);
	}
	}
	System.out.println(ans);
	}
	}

view raw gistfile1.txt hosted with ❤ by GitHub