예전에 한 번 리뷰했었던 문제인데, 지금 다시 풀어본 풀이가 좀 더 깔끔하다고 생각되어 다시 포스팅한다.
https://www.acmicpc.net/problem/1107
이동하고자 하는 목표 채널(N)을 입력받고, 고장난 버튼들을 입력받아 이 버튼들을 0~9까지의 vector에서 제외해 사용가능한 버튼들의 vector, "usableBtns"를 만든다.
// fill usableBtns vector
for (int i = 0; i < 10; i++)
{
usableBtns.push_back(i);
}
int input;
for (int i = 0; i < disalbedBtnsNum; i++)
{
cin >> input;
int inputIdx = findTargetIdx(input, usableBtns);
swap(inputIdx, usableBtns.size() - 1, usableBtns);
usableBtns.pop_back();
}
우선적으로 버튼 키를 사용하지 않고 오직 +/- 채널 이동만 사용해서 목표 채널로 이동하려면 몇 번 버튼을 눌러야 하는지 구한다.
// move only using +/-
if (currentChannel != targetChannel)
{
minBtnsNum = abs(currentChannel - targetChannel);
}
else if (targetChannel == currentChannel)
{
minBtnsNum = 0;
cout << minBtnsNum;
return 0;
}
그 다음으로는 앞서 구한 사용 가능한 버튼(usableBtns)으로 이동 가능한 번호로 이동한 후, 거기서 다시 +/- 버튼을 사용해서 목표 채널까지 이동하는 경우의 버튼 입력 수를 구한다. 이 때, 시작 채널이 100이고 목표 채널 N이 [0,500,000] 사이에 있다는 조건이 주어졌기 때문에, 나는 0~1,000,000 까지의 경우의 수만 파악하였다. 깡으로 +/- 버튼을 눌러서 이동하는 것이 인접 번호로 이동해서 +/- 버튼을 누르는 것보다 오래 걸릴 것이고, 모든 버튼이 다 고장나 있고 N = 500,000인 경우 최대 499,000 번의 채널 이동이 필요하다. 따라서 999,000 번 이상으로 이동해서 다시 -버튼을 눌러서 이동하는 경우는 불필요한 경우라고 생각하였기 때문에 배제한 것이다.
for (int i = 0; i < 1000000; i++)
{
if (isNumberReachable(i, usableBtns))
{
int newCase = countDigits(i);
newCase += abs(i - targetChannel);
minBtnsNum = min(minBtnsNum, newCase);
}
}
0~1,000,000까지 모든 경우의 수를 살펴보면서, 만일 그 번호가 usableBtns의 조합으로 만들어질 수 있다면 isNumberReachable이 true를 반환한다. isNumberReachable 함수의 return 값이 true라면, countDigits를 통해서 해당 번호로 이동하는 데 필요한 버튼 입력 수를 구하고, 거기서 다시 +/- 버튼을 통해 목표 채널에 도달하기 위한 추가 버튼 입력 수를 구한 후 이를 minBtnsNum에 update해 주는 방식으로 구현하였다.
전체 코드 첨부하고 마친다.
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <limits>
using namespace std;
void swap(int i, int j, vector<int> &v)
{
int tmp = v[i];
v[i] = v[j];
v[j] = tmp;
}
int findTargetIdx(int target, vector<int> &v)
{
int result = 0;
for (int i = 0; i < v.size(); i++)
{
if (v[i] == target)
{
result = i;
break;
}
}
return result;
}
int countDigits(int number)
{
if (number == 0)
return 1;
int cnt = 0;
while (number != 0)
{
cnt++;
number /= 10;
}
return cnt;
}
bool isNumberReachable(int number, vector<int> &v)
{
bool b = true;
vector<int> nums;
if (number == 0)
{
nums.push_back(number);
}
else
{
while (number != 0)
{
nums.push_back(number % 10);
number /= 10;
}
}
if (nums.size() == 0)
{
return false;
}
for (int i = 0; i < nums.size(); i++)
{
bool isDigitFound = false;
for (int j = 0; j < v.size(); j++)
{
if (nums[i] == v[j])
{
isDigitFound = true;
break;
}
}
if (!isDigitFound)
{
b = false;
break;
}
}
return b;
}
int main()
{
vector<int> numpadBtns;
vector<int> usableBtns;
int currentChannel = 100;
int targetChannel; // N
int disalbedBtnsNum; // M
int minBtnsNum = numeric_limits<int>::max();
cin >> targetChannel >> disalbedBtnsNum;
// fill usableBtns vector
for (int i = 0; i < 10; i++)
{
usableBtns.push_back(i);
}
int input;
for (int i = 0; i < disalbedBtnsNum; i++)
{
cin >> input;
int inputIdx = findTargetIdx(input, usableBtns);
swap(inputIdx, usableBtns.size() - 1, usableBtns);
usableBtns.pop_back();
}
// move only using +/-
if (currentChannel != targetChannel)
{
minBtnsNum = abs(currentChannel - targetChannel);
}
else if (targetChannel == currentChannel)
{
minBtnsNum = 0;
cout << minBtnsNum;
return 0;
}
for (int i = 0; i < 1000000; i++)
{
if (isNumberReachable(i, usableBtns))
{
int newCase = countDigits(i);
newCase += abs(i - targetChannel);
minBtnsNum = min(minBtnsNum, newCase);
}
}
cout << minBtnsNum;
}
'프로그래밍 > 백준 복기' 카테고리의 다른 글
[구현] 백준 1347: 미로 만들기 (0) | 2024.01.16 |
---|---|
[BruteForce] 백준 16197: 두 동전 (0) | 2024.01.09 |
[Greedy] 백준 2839: 설탕 배달 (2) | 2023.11.20 |
[BruteForce] BOJ1436: 영화감독 숌 (1) | 2023.11.15 |
[BruteForce] 백준 1018 : 체스판 다시 칠하기 (0) | 2023.03.02 |