알고리즘15 :: BOJ_1107_리모컨

이 문제는 입력으로 주어지는 수에 대해서 완전탐색, 즉 브루트포스 를 통해 해결할 수 있는 문제다.
리모컨으로 누를 수 있는 수는 0~9 까지이다.
이때 입력받는 채널은 최대 500,000인데 고장난 버튼을 고려하면 1,000,000이되어야 한다.
버튼이 6빼고 전부 고장났다고 생각해보면
입력받은 채널은 500,000 일때
66666 500,000 666,666
66666에서 500,000 을 +버튼을 누르는것보다 666,666 에서 -버튼을 누르는것이 비용적으로 덜들게된다.

접근방법은 다음과 같다.
1. 처음 시작 버튼 100번에서 +로 증가할수 있는 횟수를 파악한다.
2. 완전탐색을 진행하면서 고장나지 않은 버튼으로 입력받은 채널각각의 숫자와 몇개가 일치하는지 개수를 length로 잡고, 현재 값과 입력받은 값의 차이를 계산해서 +나 -를 얼마나할지 체크한다.
이때 +나-를 계산한 값과 length값을 더해서 최소값이되면 갱신해주고 아니면 버린다.

   이를 구현해주는 코드는 단순for문 과 재귀호출을 통해 완전탐색을 할 수 있다는 사실을 배울 수 있었다.

 

 
int arr[10];
 
memset(arr, true, sizeof(arr));

 

 

작동하지 않은 버튼을 찾기 위해 1로 초기화 한다. (*0은 고장난 버튼)

for(int i=0; i<k; i++)
{ 
 int a;
 cin>>a;
arr[0] = 0; //고장난 버튼
}

 

고장난 버튼을 표시한다.

 

int diff = abs(100-n); 

을 통해서, 100-n 즉, 가장 간단한 방법으로 n까지 + 로 찾아가는 경우를 diff에 저장한다.

 

int length, buttonPress;
 
for(int i=0; i<=1000000; i++){
 
if(i == 0)
 
        length = arr[0] ? 1 : 0;
 
for(int j=0; i>0; j++){
 
   if(!arr[i%10]
 
       length = 0
 
       length +=1;
 
       i/=10;
 
}
 
if(length>0){
 
    buttonPress = abs(length - n);     
 
   if(diff > length + buttonPress)
 
        diff = length + buttonPress;
 
}
}

 

만일에 0이 들어오면 현재 0번째 버튼이 고장인지 아닌지 판단하고 고장이 아니면

length의 길이는 1이 된다. 그리고 1일때 n과의 (=우리가 접근해야 하는 수) 차이를 통해 +를 얼마나 할지 결정하고

그것을 절댓값으로 처리하여(음수가 안나오게 하며) 결과적으로 앞으로 누를 버튼의 수와 n과의 차이를 더하게 되면 최종적으로 우리가 원하는 "얼마나 눌렀는가"를 확인할 수 있다.

그리고, 재귀적으로 탐색하는 방법을 새롭게 학습하였는데

 

void dfs(string num){
 
for(int i=0; i<10; i++){
 
        if(arr[i]){ //고장난 버튼이 아니라면
 
             string s = num + to_string(i); 
 //dfs에 매개변수로 전달되는것은 빈공간이므로 처음엔 0만있을것이다.
 
        minValue = MIN(minValue, abs(n-stoi(s))+s.length()); 
 //결국 minValue는 이전값이고 (n-stoi(s)) + s.length() 
    //는 해당 버튼이 살아있는지 체크 그리고 n 만큼 + 한것과 비교하여 최솟값을 넣어준다.      
 
    if(s.length() < 6)
 
   dfs(s); //이 다음부터 2자리             
 
      //이 부분이 무척 인상깊었다. 완전 탐색에 재귀함수를 이렇게 활용할 수 있다는것에 다시금 놀랐다.           
 
      //여기는 5번 들어가나 5번 들어간 순간 s의 자릿수는 6자리가 된다. 
 
         }
 
}
 
}
 
 

 

처음 봤을땐 굉장히 버벅 거렸는데, 관련 자료들을 찾아보니 이해하기 훨 수월 해 졌다.

특히, 재귀함수 부분은 무척 인상 깊었다.