[C++] BaekJoon 1107 리모컨

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

---

 

브루트포스 알고리즘을 사용하여, 일일히 계산하였다.

이때 시작 채널은 100이므로, 100에서 목표 채널을 뺀 수와, 근사치를 구해 횟수를 카운트 한 수를 비교해

더 적은 수를 최종 결과로 출력한다. 

 

코드

#include <iostream>
#include <vector>
#include <cmath>
#include <climits>
#include <string>
#include <algorithm>

using namespace std;

int countDigits(int target, int number) { //횟수
    //카운트 비교군 a,b / 이 중 비교하여 카운트가 적은 수를 선택한다. 
    int count_a = abs(target - number); //목표 값 - 근삿값 = 횟수
    int count_b = abs(100 - target); //Reason. 예를 들어 target이 101일 때는 채널을 한번 증가시키는게 더 빠르다
    
    if (number == 0) //근삿값이 0일때는 자릿수 계산이 불가능함, Count 증가
    {
        count_a++;
    }

    while (number != 0) { //자릿 수 계산, 자릿수가 곧 Count
        number /= 10;
        count_a++;
    }

    int count = min(count_a, count_b); //비교
    return count;

}

int FindNumber(int num, const vector<int>& Numbers) //리모컨으로 목표 채널에 근접한 수 입력 함수
{
    int closest = INT_MAX; // 최소값을 최대로 초기화
    int closestDiff = INT_MAX; // 차이의 절댓값을 최대로 초기화

    for (int i = 0; i <= 1000000; ++i) { // 범위는 임의로 설정
        bool exclude = false;
        for (int digit : Numbers) {
            if (to_string(i).find(to_string(digit)) != string::npos) {
                exclude = true;
                break;
            }
        }
        if (exclude) // 사용하지 않는 숫자를 가진 수는 건너뜀
            continue;

        int diff = abs(num - i);
        if (diff < closestDiff) {
            closestDiff = diff;
            closest = i;
        }
    }

    return closest;
}

int main()
{
	int N,M;
	int Num;
	vector<int> BanNumbers; //고장난 숫자
	cin >> N;
	cin >> M;
	for (int i = 0; i < M; i++)
	{
		cin >> Num;
		BanNumbers.push_back(Num);
	}
    
    if (N == 100) //N이 100일 때는 계산할 필요가 없음, 0 출력
    {
        cout << 0;
        return 0;
    }

    if (M == 10) //모든 숫자키가 고장났을 때는 일일히 증감시켜야함, 100에서 목표 값을 뺀 절댓값을 출력
    {
        cout << abs(100 - N);
        return 0;
    }

	int closet = FindNumber(N, BanNumbers); //근사값 계산 함수 


    int digits = countDigits(N, closet); //근사값을 토대로 카운트 계산
	cout << digits;

	return 0;

}

설명

고려해야 할 조건이 꽤 많다.

먼저 고장난 숫자 키를 벡터에 넣는다. 

 

Case I. 만약 N이 100일 때는 계산할 필요가 없다. -> 0 출력

Case II. 모든 숫자키가 고장났을 때는 카운트를 일일히 증감시켜야한다. 모든 숫자키가 고장났다는 것은 M = 10임을 의미한다. -> 시작 채널에서 목표값을 뺀 절대값을 출력

 

위의 두 조건에 해당하지 않으면 근삿값을 찾는다. 

 

근삿값을 구하는 함수에서 for문 범위를 1,000,000으로 설정하였는데 이는 최대 채널은 500,000이고

그렇기에 리모컨으로 만들수 있는 가장 큰 숫자는 999,999이기 때문에 1,000,000으로 설정하였다.

 

반복문을 실행하면서 벡터에 있는 숫자가 포함될 때, 건너뛰고 다음으로 넘어간다.

그리고 목표값과 탐색값을 뺀 값이 가장 적은 수를 계산한다. 

int Closet이라고 선언하였다. 

 

Closet과 N(목표값)을 가지고 버튼을 누른 횟수를 카운트한다. 

 

Case III. 100에서 채널을 시작한다는 점을 기억해야한다. 

근삿값을 구해 숫자를 입력하는 것 보다, 100에서 채널을 증감하는것이 더 빠른 경우가 있다.

예를 들어 목표 채널이 101일 경우 근삿값을 구하는거 보다 증감하는 횟수가 더 빠르다. 

이 경우, 두가지 계산을 수행한다.

Count_A = 목표값에서 근삿값을 뺀 절댓값 + 자릿수(카운트) 

Count_B = 100 - 목표값을 뺸 절댓값

이 후 두 수를 비교하여 더 적은 수를 최종 결과로 출력한다. 

 

Case IV. 근삿값이 0일 때는 자릿수 계산이 불가능하다. (0을 10으로 나눴을 때, 정상적인 결과가 도출되지 않음)

이때는 Count를 증가시킨다.