풀이
정말 간단한 문제처럼 보이지만
실상 제어해 줘야 하는 조건이 상당히 많은 boj 1107 번 리모컨 문제입니다.
코드 이해에는 크게 무리가 없을 만큼 단순함으로
제어 해 줘야 할 조건들만 짚어 보고 가겠습니다.
가능 한 숫자들중에서 왼쪽 끝을 lefttop 오른쪽 끝을 right top 으로 정해줍니다.
(예를 들어 가능한 숫자가 3, 5 , 6 , 7 이면 left top = 3, right top = 7)
우선 기본적으로, 처음으로 불가능 한 숫자가 나올때 까지 +- 해주며 왼쪽이나 오른쪽으로 움직이며 가능 한 숫자를 찾아줍니다.
예를 들어 5678 을 찾는데
만약 숫자 6,7이 불가능 하다면,
앞에서부터 천천히 확인을 해 나갑니다.
5->? 가능 ? 가능 -> 넘어가기
6-> 가능? -> 불가능
- 왼쪽 출발 - 4-> 가능? 가능 : 54XX 로 바꿈. 왼쪽 방향임으로 right tpo인 9로 나머지 자리를 채움(아래로 내려왔으니 윗방향 채널돌리려면 제일 큰거로 채워야 가장 빠름.
=> 5499 채널로 이동 후 5678-5499 만큼 + 를 누르면 이동이 가능
- 오른쪽 출발 - 7 가능? 불가능, 8 가능? 가능 58XX 로 바꿈. 왼쪽과는 반대로 lefttop으로 나머지를 채움
=> 5800 채널로 이동 후 5800 - 5678 만큼 -를 누르면 이동이 가능.
이런식으로 확인을 해주면 됩니다.
-
1자리 숫자에서 잘 작동 되는가?
-
첫 자리가 불가능 하며, right top 보다 커서 오른쪽으로 이동이 불가능함.
- 이럴때는 한자리를 추가시켜 left top 으로 싹 채워 주면 됩니다.
예를 들면 1 만 가능 한데, 9000이라는 숫자가 왔다고 생각해봅시다.
왼쪽으로 가면 1111을 얻고, 9000-1111 만큼 이나 버튼을 눌러 줘야 합니다.
오른쪽으로 가려는데 오른쪽으로 갈 수가 없습니다. 그럼으로 한자리를 늘려서
11111 로 만들어주고, 11111-9000 만큼 버튼을 눌러주면 되는겁니다.
이는 반대로 left top 이 걸리는 것도 마찬가지입니다. !
딱 반대로 해주시면 됩니다.
그외 / 저는 최소값을 찾기 위해 priority_queue 를 사용 하였습니다.
비교 해야할 갯수가 적기에 굳이 priority_queue 를 사용 할 필요는 없지만
귀찮아서…
또 priority_queue 도 미리미리 쓰는 연습을 꼭 해두셔야합니다. !
필요할 때가 분명히 있기 때문이죠
코드
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <functional>
using namespace std;
int un[] = { 1,1,1,1,1,1,1,1,1,1 };
int originN;
int leftTop = -1;
int leftNzTop = 0;
int rightTop = 0;
priority_queue<int, vector<int>, greater<int>> result;
int toLeft(vector<int> chanel, int start, int rightTop) {
int rollback = 0;
int zeroCount = 0;
for (int i = start; i < chanel.size(); i++) {
chanel[i] = rightTop;
}
for (int i = 0; i < chanel.size(); i++) {
rollback = rollback * 10 + chanel[i];
}
return (chanel.size() + abs(rollback - originN) - zeroCount);
}
void checker(vector<int> chanel,int i) {
int findCoin = 1;
int left, right;
left = chanel[i];
right = chanel[i];
while (findCoin) {
left -= 1;
right += 1;
if (left == -1 && right == 10) {
break;
}
if (left == -1)
left = 0;
if (right == 10)
right = 9;
if (un[left] == 1) {
findCoin = 0;
chanel[i] = left;
result.push(toLeft(chanel, i + 1, rightTop));
}
if (un[right] == 1) {
findCoin = 0;
chanel[i] = right;
result.push(toLeft(chanel, i + 1, leftTop));
}
}
}
int main() {
int n;
int ern;
int temp;
int count = 0;
int i;
int findCoin = 1;
stack<int> chan;
vector<int> chanel;
cin >> n >> ern;
originN = n;
for (int i = 0; i < ern; i++) {
cin >> temp;
un[temp] = 0;
}
for (int i = 0; i <= 9; i++) {
if (un[i] == 1) {
rightTop = i;
if (leftTop == -1)
leftTop = i;
if (leftNzTop == 0)
leftNzTop = i;
}
}
result.push(abs(n - 100));
chan.push(n % 10);
n /= 10;
while (n != 0) {
chan.push(n % 10);
n /= 10;
}
while (!chan.empty()) {
chanel.push_back(chan.top());
chan.pop();
}
if (ern == 0) {
result.push(chanel.size());
}
else if (ern == 10) {
}
else {
for (i = 0; i < chanel.size(); i++) {
if (un[chanel[i]] == 0)
break;
}
if (i == chanel.size()) {
result.push(chanel.size());
}
else {
for (int j = 0; j <= i; j++) {
checker(chanel, j);
}
}
temp = 0;
int i = 0;
if (leftTop == 0) {
temp = leftNzTop;
i++;
}
for (; i <= chanel.size(); i++)
temp = temp * 10 + leftTop;
if (temp <= 500000)
result.push(abs(originN - temp)+ chanel.size() + 1);
temp = 0;
for (int i = 1; i < chanel.size(); i++)
temp = temp * 10 + rightTop;
if (chanel.size() == 1)
temp--;
if (temp != -1 || rightTop == 0) {
result.push(abs(originN - temp) + chanel.size() - 1);
}
}
cout << result.top();
cin >> n;
return 0;
}