•
접근 방법
처음 접근했던 방법은, 브루트포스로 풀기 보다는 리모콘으로 최대한 그 채널과 근접하게 이동 후에 채널의 차이를 구하는 방식으로 생각했습니다. 또한 이동하려는 채널보다 큰 값과 작은 값 두 부분으로 나누어서 계산하려고 했습니다. 예를 들어, 이동하려는 채널의 번호가 2333 이라고 하면 2,3의 버튼이 고장 났다고 가정할때 3000가 큰 값, 1999가 작은 값이라 생각하고 코드를 작성했습니다. 하지만 이 방법의 문제점은 999 와 같은 값을 원하는 채널로 받았을때 예외케이스가 많이 발생한다는 것이었습니다. 가령 8과 9의 채널이 고장났다면 999보다 큰 값인 1000 을 찾아내야 하는데 그 값을 계산하기 위해서는 결국 브루트포스로 찾아낼 수 밖에 없다는 생각이 들었습니다.
브루트포스 방식으로 계산할 경우 N의 최대값은 500,000이므로 (10의 6승 * 계산하는 각 숫자의 자릿수의 합)이 시간복잡도로 나왔습니다. 따라서 다른 기법을 사용하지 않고 브루트포스를 이용하여 정답을 찾아낼 수 있었습니다.
#include <iostream>
#include <vector>
#include <cstdlib>
int N, M;
std::vector<int> b_channel;
int c_min, c_size;
void input_faster()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
}
void input()
{
int tmp;
input_faster();
std::cin >> N >> M;
b_channel.resize(10, 1);
for (int i = 0 ; i < M; i++)
{
std::cin >> tmp;
b_channel[tmp] = 0;
}
}
int is_possible(int n)
{
c_size++;
if (n <= 9)
{
if (b_channel[n])
return (1);
else
return (0);
}
if (is_possible(n / 10))
{
if (b_channel[n % 10])
return (1);
}
return (0);
}
void print_val()
{
std::cout << c_min;
}
void solve()
{
c_min = std::abs(N - 100);
for (int i = 0 ; i <= 1000000 ; i++)
{
c_size = 0;
if (is_possible(i))
if (std::abs(N - i) + c_size < c_min)
c_min = std::abs(N - i) + c_size;
}
}
int main()
{
input();
solve();
print_val();
return (0);
}
C++
복사
