[baekjoon 백준] 1107 - 리모컨 : c++ 문제풀이

문제 접근:

1. 목표 채널 번호 또는 목표 채널 가장 가까이 접근해서 경우의 수를 비교하며 누르는 버튼의 최소 수를 갱신

2. 일단 고장난 버튼이 포함되면 제외

3. 누르는 버튼의 최소수 -> 기본값: 처음 위치 100에서 +-로 접근 -> 근접한 채널로 이동(채널번호의 자릿수 계산) + +-로 이동(목표 채널과의 차이 계산)

 

목표채널이 고장난 버튼의 숫자를 포함하고 있을 때가 문제상황 -> 그럼 목표 채널의 앞뒤를 왔다 갔다하며 최소 수를 구할 것인가..?

-> 쫌 복잡함.. 목표 채널에 근접한 채널에 포함된 숫자 버튼들이 모두 고장났을 경우는 어차피 앞뒤로 수 많은 경우의 수를 훑어야함

-> 그냥 모든 경우의 수 (0 ~ (500000-100)*2 정도) 훑는게 속 편하다~

-> 결론은 brute force 부르트 포스 알고리즘!

 

 

 

#include <iostream>
#include <cmath> //절댓값 abs 사용
#include <algorithm> //최소값 min 사용
using namespace std;

int broken[10] = {0,0,0,0,0,0,0,0,0,0}; //고장난 키 기록(전역)

//숫자 n에 고장난 키 포함되어 있으면 false, 아니면 true 반환하는 함수
bool possible(int n){ 
  if (broken[n%10] == 1){
    return false;
  }
  n /= 10;
  while (n>0){
    if (broken[n%10] == 1){
      return false;
    }
    n /=10;
  }
  return true;
}

//채널 번호의 자릿수 계산하는 함수
int digit(int n){
  int num= 1;
  n /=10;
  while (n>0){
    num++;
    n /= 10;
  }
  return num;
}

int main() {
  int target;
  int n;
  
  cin >> target >> n;
  int tmp;
  if (n>0){
    for (int i = 0; i< n; i++){
      cin >> tmp;
      broken[tmp] =1;
    }
  }
  
  //기본값: 원위치 100에서 +-로 이동하는 경우
  int answer = abs(target - 100);
  
  //모든 경우의 수 훑으면서 최소 갱신
  for (int i = 0; i<1000000;i++){
    if (possible(i)){
      int minimum = abs(target - i); //i에서 목표채널까지 +-로 이동하는 수
      answer = min(answer, digit(i) + minimum); //채널번호 누르고 +-로 이동하는 수가 answer보다 작으면 갱신
    }
  }
  
  cout << answer;
  return 0;
}

세 번 정도 시도 후에 성공했는데 첫 번째에는 possible 함수에서 n>0을 조건으로 반복문을 돌린탓에 <채널 번호가 0이고, 고장난 버튼에 0이 포함될 경우> false로 반환하지 못해 틀렸고, 두 번째에도 0이 한자리 수라는 것을 간과했고 <채널을 0으로 돌려야하는 경우> digit계산에서 1이 아닌 0으로 틀린 값이 나와왔다. 주의하도록 하자~!