1107 리모컨[G5]

 

문제

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

1107번: 리모컨

 

수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다.

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

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

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

 

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

 

풀이

 

전형적인 재귀 함수 사용 문제이다.

버튼을 누를 수 있는 경우의 수를 remote[] 배열에 저장했고,

1자리부터 6자리(최대 500000이므로)의 버튼을 누른다 가정하고 모든 경우의 수를 판단했다.

최악의 경우에도 시간 복잡도가 2초 내에 해당할 수 있을 것이라 판단했다.

 

자세한 내용은 주석을 참고할 것.

코드

import java.io.*;
import java.util.*;
/*
1. 먼저 M개에 맞는 채널 개수만큼 입력
2. 해당 채널이 결과값과 얼마나 차이나는지 확인
3. 백트래킹 사용

최대 N = 500000 .. 6자리
경우의 수 : 10^6 = 1000000
5자리, 4자리 .. 가 더욱 효율적일 수도 있다. 결국 다 구해봐야 한다.
*/

class Main {
  static final int CHANNAL = 100;
  static int N;
  static int M;
  static int remote[];
  static int result; //결과
  public static void main(String[] args) throws Exception{
    //입력
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    N = Integer.parseInt(br.readLine());
    M = Integer.parseInt(br.readLine());
    HashSet<Integer> broken = new HashSet<Integer>();
    
    //고장난 버튼이 있다면 추가하기
    if(M > 0) {
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	for(int i = 0; i < M; i++) broken.add(Integer.parseInt(st.nextToken()));
    }

    //리모컨 버튼 누를 수 있는 경우를 담는 배열
    remote = new int[10 - M];
    int idx = 0;
    for(int i = 0; i < 10; i++) {
      if(broken.contains(i)) continue;
      remote[idx++] = i;
    }

    // +1 -1만 했을 때 나오는 결과
    result = Math.abs(N - CHANNAL); 
    
    //리모컨 누르는 회수(1자리 ~ 6자리)
    for(int i = 1; i <= 6; i++) {
      solve(i, 0, 0);
    }

    System.out.println(result);
  }

  static void solve(int maxButtonCount, int nowButtonCount, int totalCount) {
	  if(maxButtonCount == nowButtonCount) { //버튼 총 사용량 체크
		  result = Math.min(result, Math.abs(totalCount - N) + maxButtonCount);
      return;  
    }

    totalCount *= 10; //자리수 추가
    
    for(int i = 0; i < remote.length; i++) {
      solve(maxButtonCount, nowButtonCount + 1, totalCount + remote[i]);
    }
  }
}