백준 1107번
오늘 풀어본 문제는 백준의 1107번 문제1이다. 문제 풀이에 사용한 언어는 C++ 이다.
solved.ac 기준 CLASS
문제 정보
이 문제의 내용과 조건은 다음과 같다.
문제
수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다.
리모컨에는 버튼이 0부터 9까지 숫자, $+$와 $-$가 있다. $+$를 누르면 현재 보고있는 채널에서 $+1$된 채널로 이동하고, $-$를 누르면 $-1$된 채널로 이동한다. 채널 $0$에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다.
수빈이가 지금 이동하려고 하는 채널은 $N$이다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오.
수빈이가 지금 보고 있는 채널은 $100$번이다.
입력
첫째 줄에 수빈이가 이동하려고 하는 채널 $N$ $(0 \leq N \leq 500,000)$ 이 주어진다. 둘째 줄에는 고장난 버튼의 개수 $M$ $(0 \leq M \leq 10)$ 이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주어지며, 같은 버튼이 여러 번 주어지는 경우는 없다.
출력
첫째 줄에 채널 $N$으로 이동하기 위해 버튼을 최소 몇 번 눌러야 하는지를 출력한다.
풀이과정
첫 번째 시도
이 문제는 겉보기에는 간단해보이는 문제이다. 특별히 요구하는 복잡한 자료구조도 없고, 그냥 순수하게 구현을 하면 되는 문제이다. 하지만 이걸 실제로 코드로 짜는 것은 다른 문제이다. 여러 가지 풀이 방법을 생각해봤지만, 구현이 복잡한 이유 등으로 코드를 짜는데 생각보다 오래 걸렸다.
내가 이 문제를 푼 방식을 간단하게 설명하면 다음과 같다.
-
채널은 100번에서 시작하니까 100번에서 목표 채널로 이동하기까지 눌러야 하는 버튼의 횟수를 우선 최솟값으로 결정한다.
-
목표 채널의 자릿수가 몇 개인지 확인하고, 그 자릿수 $+1$ 만큼의 자릿수를 가진 숫자들을 만든다. $+1$ 을 해주는 이유는, 목표 채널이 $999$ 인 식의 케이스에 대해서 자릿수가 하나 많은 수까지는 고려해주어야 하기 때문이다. 수를 만드는 과정에서는 고장나지 않은 버튼만 사용한다.
-
만들어진 수들을 저장해두고, 마지막에 목표 채널까지 도달하기 위해 눌러야 하는 키의 개수를 확인하여 최솟값을 결정한다.
지금 와서 정리 해보면 딱히 어려울 것이 없어보이는 말이지만, 앞에서도 말했던 것 처럼 이걸 떠올려서 코드로 구현하는데는 생각보다 힘들었다.
코드는 다음과 같이 작성하였다.
#include <bits/stdc++.h>
using namespace std;
vector<int> brokenButtons;
vector<int> notBrokenButtons = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
vector<int> numbersToCheck;
int getDigits(int number);
void makeNumber(int formerNumbers, int digits);
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int minimum;
int targetChannel, numberOfBrokenButtons, digits;
cin >> targetChannel;
cin >> numberOfBrokenButtons;
for (int i = 0; i < numberOfBrokenButtons; i++) {
int tempButton;
cin >> tempButton;
brokenButtons.emplace_back(tempButton);
notBrokenButtons.erase(remove(notBrokenButtons.begin(), notBrokenButtons.end(), tempButton), notBrokenButtons.end());
}
minimum = abs(targetChannel - 100);
digits = getDigits(targetChannel);
for (int i = 1; i <= min(6, digits + 1); i++) {
makeNumber(0, i);
}
for (auto i : numbersToCheck) {
minimum = min(minimum, getDigits(i) + abs(targetChannel - i));
}
cout << minimum;
return 0;
}
int getDigits(int number) {
if (number < 10) {
return 1;
}
else if (number < 100) {
return 2;
}
else if (number < 1000) {
return 3;
}
else if (number < 10000) {
return 4;
}
else if (number < 100000) {
return 5;
}
else {
return 6;
}
}
void makeNumber(int formerNumbers, int digits) {
for (auto i : notBrokenButtons) {
if (digits == 1) {
numbersToCheck.emplace_back(formerNumbers * 10 + i);
}
else {
makeNumber(formerNumbers * 10 + i, digits - 1);
}
}
}
그러자 모든 테스트 케이스를 통과하고 정답이 나오는 것을 확인할 수 있었다.
두 번째 시도
평소같았으면 이 문제는 여기서 끝났겠지만, 코드를 되돌아보니 안쓰이는 변수들도 있었고, 코드도 좀 더 깔끔하게 다듬을 수 있는 부분들이 보였다. 이미 눈치를 채버린 이상 가만히 둘 수는 없었고, 코드는 다음과 같이 수정하여 재제출하였다.
#include <bits/stdc++.h>
using namespace std;
int getDigits(int number);
void makeNumber(int formerNumbers, int digits, vector<int>& availableButtons, vector<int>& numbersToCheck);
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int minimum;
int targetChannel, numberOfBrokenButtons;
vector<int> availableButtons = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
vector<int> numbersToCheck;
cin >> targetChannel;
cin >> numberOfBrokenButtons;
for (int i = 0; i < numberOfBrokenButtons; i++) {
int tempButton;
cin >> tempButton;
availableButtons.erase(remove(availableButtons.begin(), availableButtons.end(), tempButton), availableButtons.end());
}
minimum = abs(targetChannel - 100);
for (int i = 1; i <= min(6, getDigits(targetChannel) + 1); i++) {
makeNumber(0, i, availableButtons, numbersToCheck);
}
for (auto i : numbersToCheck) {
minimum = min(minimum, getDigits(i) + abs(targetChannel - i));
}
cout << minimum;
return 0;
}
int getDigits(int number) {
int digits = 0;
if (number == 0) {
return 1;
}
else {
while (number > 0) {
number /= 10;
digits++;
}
return digits;
}
}
void makeNumber(int formerNumbers, int digits, vector<int>& availableButtons, vector<int>& numbersToCheck) {
for (auto i : availableButtons) {
if (digits == 1) {
numbersToCheck.emplace_back(formerNumbers * 10 + i);
}
else {
makeNumber(formerNumbers * 10 + i, digits - 1, availableButtons, numbersToCheck);
}
}
}
이번에도 물론 모든 테스트 케이스를 통과하고 정답이 나오는 것을 확인할 수 있었다.
마무리
이 문제의 CLASS는 3이기는 하나, 개인적으로 매우 인상깊은 문제였다. 그래서 굳이 블로그 글로 남기는 것이기도 하다. 문제 자체는 PS를 위한 복잡한 사전지식이 필요한 것은 아니지만, 문제를 해결하기 위한 전략을 수립하고 구현한다는 PS (Problem Solving)의 본질에 매우 충실한 문제였다고 생각했기 때문이다.
이 문제는 앞에서도 이야기했지만 별다른 사전 지식이 필요한 문제가 아니다. 그럼에도 불구하고 CLASS 3, Gold V 난이도라는 것은 그만큼 난이도가 있는 문제라고 할 수 있다. 지금와서 하는 이야기지만, 문제를 푸는 동안에는 머리가 아프고 귀찮았지만, 이런 문제들이 진짜 재미있는 문제인 것 같기도 하다. 앞으로 자주 만날 수 있었으면 좋겠다.
오늘의 PS는 여기까지!
1: https://www.acmicpc.net/problem/1107