[브루트포스] 백준 - 리모컨

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

1107번: 리모컨

 

-문제해설

처음에 dfs로 풀다가 머리가 깨질뻔했다... 욕나오고; 어떻게하면 풀 수는 있을 것 같은데 아직 내 실력이 부족한 것 같다 ㅎ

 

일단 이 문제를 통해서 최적의 해를 구하는 문제가 나오면 일단은 탐색방법으로 접근을 하고 

탐색방법중에서 가능한 방법을 먼저 적용해야겠다는 노하우가 생겼다.

완전탐색이나 이분탐색 등의 방법을 생각하면 될 것 같다.

 

1. n,m을 입력받는데 m이 0 인 경우(=리모컨 버튼이 하나도 고장나지 않은 경우)를 생각해야 한다.

 

2. boolean타입의 remocon[] 변수에 고장난 버튼의 숫자 인덱스값만 true로 초기화해준다.

   remocon[ 고장난숫자 ] = true

 

3. 완전탐색을 위해 가능한 리모컨으로 누를 수 있는 모든 채널을 탐색한다. 먼저 n의 최대범위가 500_000 6자리이기 때문에 리모컨으로 만들 수 있는 채널의 범위는 0~999_999이다. 반복문을 통해 0번 채널부터 999_999채널까지 순회한다.

 

4. 완전탐색 코드는 이해하기 쉽게 예를 들자면

n=9이고 고장난 버튼이 2 4 6일 경우

0번 채널의 ans는 0버튼을 누른 횟수(1) + 0에서 9까지의 차(9) = 1+9 = 10

1번 채널의 ans는 1버튼을 누른 횟수(1) + 1에서 9까지의 차(8) = 1+8 = 9

2번 채널의 경우 고장났으므로 패스

3번 채널의 ans는 3버튼을 누른 횟수(3) + 3에서 9까지의 차(6) = 1+6 = 7

이런식으로 진행하면 되고

 

만약 n이 세자리수일 경우

n=123이고 고장난 버튼이 2 3일 경우

0번부터 진행되다가 100번 채널인 경우

100번 채널의 ans는

     먼저 1버튼이 고장나지 않고

     0버튼이 고장나지 않고

     0버튼이 고장나지 않으면

100채널을 만들기 위해 버튼 누른 횟수(3) + 100에서 123까지의 차(23) = 3+23 = 26

 

120번 채널의 ans는

    1버튼이 고장나지 않았지만

    2버튼은 고장이므로 다음 채널로 이동한다.

 

121번 채널의 ans는 

    1버튼이 고장나지 않았지만

    2버튼은 고장이므로 다음 채널로 이동한다.

 

이런식으로 진행된다.

 

이를 코드로 보게되면

channel은 채널의 자리수가 줄어들때마다 값을 저장하는 변수 (현재 채널이123인 경우: 123 -> 23 -> 3 )

pow는 channel변수의 자리수를 줄이기 위한 변수 ( 10의 제곱 )

chk는 현재 채널의 버튼 중에서 고장난 버튼이 있는 경우 다음 채널로 이동하기 위한 boolean변수

buttonCnt는 현재 채널의 버튼수 ( 현재 채널이 123인 경우 버튼수는 3 )

 

 

5. 현재 채널의 버튼중에 고장난게 있으면 다음 채널로 이동하고, 고장난게 없다면 ans를 구해서 기존 ans와 비교한다.

 

6. 최종적으로 ans를 출력하면 끝.

 

 

-자바

package bruteforce;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BJ1107 {
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt( br.readLine() );
		int m = Integer.parseInt( br.readLine() );
		
		boolean[] remocon = new boolean[10]; //0~9번까지있는 리모컨
		
		//리모컨 버튼이 하나도 고장나지 않은 경우를 위해서 if문을 사용한다.
		if( m != 0 ) {
			StringTokenizer st = new StringTokenizer( br.readLine() );
			int tmp_broke = 0;
			for( int i=0; i<m; i++ ) {
				tmp_broke = Integer.parseInt( st.nextToken() );
				remocon[tmp_broke] = true;	//true이면 고장난 것.
			}
		}
		
		int ans = Math.abs( n - 100 );
		int tmp_ans = Integer.MAX_VALUE;
		
		//왜 완전탐색을 해야하는가? : dfs로하려다가 겁나꼬여서 실패...ㅅㅂ
		//일단 최적의해를 찾는 문제라면 완전탐색을 먼저 떠올리자 !
		//0번채널부터 999_999채널까지 순회하면서 
		//각 채널에서 n채널을 만드려면 몇 번의 버튼을 눌러야되는 지 구한다.
		for( int i=0; i<=999_999; i++ ) {
			int channel = i;
			int pow = 0;//channel의 자리수를 구할 때 필요한 변수(ex: 100 -> 10을 만들기 위해 필요함)
			boolean chk = false;//현재 channel의 버튼중에 하나라도 고장났을 때의 경우를 나눠주는 변수
			int buttonCnt = (i+"").length();//누르는 버튼 수 (예시: 123이면 3개버튼 누르게된다)
			
			for( int j=buttonCnt; j>0; j-- ) {//버튼 수만큼 반복		
				pow = (int)Math.pow( 10, j-1 );
				
				if( remocon[ channel/pow ] ) {//해당 버튼이 고장났을 경우
					//현재 channel에서 하나의 버튼이라도 고장났으면
					//계산을 그만하고 다음 채널로 넘어간다.
					chk = true;	 
					break;
				}
				
				//위에 for문에서 버튼이 고장 안났으면 channel의 자리수를 하나 내려준다. 
				channel -= (channel/pow)*pow;
			}
			
			
			//위에 for문에서 channel의 버튼이 하나라도 고장났으면 chk=true이므로 다음 채널로 넘어가고
			//버튼이 고장안났다면 버튼수+(n-현재채널)을 구한 다음 ans값과 비교한다.
			if( chk ) continue;
			else {
				tmp_ans = buttonCnt + Math.abs( n - i );
				ans = Math.min( ans, tmp_ans );
			}
		}
		
		System.out.println( ans );
	}
}

 

 

-파이썬

from sys import stdin
import math

input = stdin.readline
n = int(input())
m = int(input())

remocon = [False]*10
if m!=0: 
    tmp_list = list( map(int, input().split()) )
    for i in tmp_list: remocon[i] = True

ans = abs( n - 100 )

for i in range( 1000000 ):
    channel = i
    chk = False
    buttonCnt = len( str(i) )

    for j in range( buttonCnt, 0, -1 ):
        v_pow = math.pow( 10, j-1 )
        if remocon[ int( channel//v_pow ) ]:
            chk = True
            break
        
        channel -= (int(channel//v_pow))*v_pow
    
    if( chk ): continue
    else: 
        ans = min( [ ans, buttonCnt+abs( n-i ) ] )
print( ans )