#1107: 리모컨
문제:
수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다.
리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다.
수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오.
수빈이가 지금 보고 있는 채널은 100번이다.
입력:
첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주어지며, 같은 버튼이 여러 번 주어지는 경우는 없다.
풀이:
- 이 문제는 구현을 시도해보았지만 풀면 풀 수록 생각지 못한 경우로 인하여 많은 조건들이 추가되면서 코드가 너무 길어졌고 결국에는 풀지 못하였다. 그래서 occidere님의 블로그 포스팅에서 풀이법을 찾아본 뒤 풀었다. 타 풀이법과 다르게 occidere님의 풀이가 좋았던 점은 코드 구현을 설명하는 다른 포스팅과는 다르게 이 문제를 풀기 위한 핵심이 무엇인지 알려주셨기 때문이다.
- 내가 처음에 구현을 시도한 방식은 각 자리수마다 가까운 숫자를 찾은 뒤 +,-를 누르는 거였는데 occidere님의 풀이를 보면 이러한 방식의 문제점을 정확히 말씀해 주시고 이 문제를 풀기 위한 핵심을 한줄로 요약하여 말씀해주신다.
- occidere님의 핵심은 바로 복잡한 수학 방식이 아닌 모든 부서진 버튼을 제외한 모든 버튼을 누르는 경우의 수를 구한 뒤 그것을 비교하는 것이다(추가적으로 100에서 +,-를 누르는 경우도 비교해준다). 이미 브루트 포스 알고리즘을 이용하여 푸는 문제임에도 불구하고 이 방식을 생각을 못 해봤다는게 조금 부끄럽다. 항상 코딩을 하다보면 어떻게 하면 효율적으로 짤 수 있을까라는 생각부터 하기 때문에 저 당연한 생각을 하지 못한 것이다. 이 문제를 통해 느낀점은 표현이 좀 그럴 수 있지만 브루트 포스는 정말 무식함의 끝을 보여주어야 되는 문제라고 생각 된다.
- 이제 구현을 설명하겠다. 우선 모든 입력을 받고 고장난 버튼은 bool자료형의 배열에 고장난 버튼의 인덱스만 true로 바꾸어 저장해준다. 그리고 제일 기본적인 방법인 100에서 +,-만 누르는 경우를 answer에 저장해준다.
- 이제 모든 숫자 버튼이 고장난 경우를 제외하고 가능한 채널의 모든 경우의 수를 재귀함수로 구현할 것이다. 우선 0부터 10까지 for문으로 문자열을 조합하여 만든다. 이때 고장난 버튼이면 조합을 만들 때 제외한다. 현재 만든 조합과 answer와 비교하여 만든 조합이 횟수가 더 적을 경우 answer에 저장한다. 그리고 만약에 길이가 6보다 작다면 재귀함수로 생성한 문자열을 가지고 들어가서 뒷자리에 추가로 숫자를 더 해준다. 이렇게하면 뒷자리부터 모든 경우의 수를 다 넣어보면서 할 수 있다. 그리고 재귀함수가 끝나면 answer에는 최종적으로 제일 작은 값이 저장 되어 있을 것이다.
⚠️answer에 저장 시 min함수를 이용하면 컴파일러가 다른 자료형으로 인식하고 컴파일 오류가 뜬다. 이 문제는 temp_n.length()에서 비롯된 건데 그 이유는 .length()가 반환하는 값이 byte값이기 때문에 int 자료형과 같은 특정 자료형이 아니기 때문이다. 자세한 내용은 이 영어로 된 링크를 확인해보면 된다. 하지만 if문과 같은 ? … : …를 이용하면 크기 비교가 가능하기 때문에 MIN을 define 해준 것이다.
코드:
#include <iostream>
#define MIN(a,b) (a<b ? a : b)
using namespace std;
int n, m, answer = 500001, counter = 0;
bool broken[10]={};
//모든 버튼을 누르는 경우의 수를 확인하는 재귀함수
void brute_force(string n_string){
//0부터 9까지 모든 버튼 확인
for(int i=0; i<10; i++){
//고장난 버튼 제외하고 실행
if(!broken[i]){
//가능한 버튼 조합 생성
string temp_n = n_string + to_string(i);
//채널과 현재 조합된 숫자와의 거리+누른 버튼 수
answer = MIN(answer, abs(n-stoi(temp_n))+temp_n.length());
//아직 6자리 안채웠다면 6자리 채울 때까지 더 해보기
if(temp_n.length() < 6) brute_force(temp_n);
}
}
}
int main(){
//입력
cin >> n;
cin >> m;
for(int i = 0; i < m; i++){
int temp;
cin >> temp;
broken[temp] = true;
}
//100에서부터 +,-를 누르는 경우
answer = min(answer, abs(n-100));
//모든 버튼이 안되는 경우를 제외하고 모든 버튼의 경우의 수에
//따른 거리 계산 함수 실행
if(m!=10){
brute_force("");
}
cout<<answer;
}
Leave a comment