[백준] 1107번 : 리모컨 - C/C++

 

문제를 읽고 바로 풀이 과정이 떠오르지는 않았다.

그 이유는 문제 자체를 이해 못했기 때문.

문제에서 요구하는 내용을 정리하면 다음과 같다.

 

리모컨을 이용해서 채널 n으로 이동할 때, 버튼을 최소로 누르는 문제이다.

리모컨은 0~9까지의 숫자 버튼과 +/- 버튼이 있다.

일부 숫자 버튼이 고장났을 수 있기 때문에 이 부분까지 고려해야 한다.

(고장난 버튼의 수와 번호는 사용자가 입력함)

 

문제 풀이 순서는 다음과 같다.

1. 채널 입력 받기

2. 동작하지 않는 버튼 입력하기

3. 결과 출력

 

당연한 과정을 설명했다.

 

이제 문제를 풀어보자.

 

크게 두 단계로 문제 풀이를 할 수 있다.

 

• +/- 버튼만 사용하는 경우
  • 현재 채널은 100이므로, |100 - N| 만큼 +/- 버튼을 눌러 이동할 수 있다.
  • 이를 초기 최소 횟수로 설정한다.
• 숫자 버튼을 사용하는 경우
  • 0~999999까지의 모든 숫자에 대해, 해당 숫자를 숫자 버튼으로 입력할 수 있는지 확인한다.
  • 입력할 수 있다면, 숫자를 누른 후 +/- 버튼으로 N까지 이동하는 횟수를 계산한다.
  • 두 가지 방법 중 최소 횟수를 선택한다.

728x90

배열로 고장난 숫자 버튼을 입력받을지 고민을 하다가,

요즘은 벡터(vector)로 알고리즘 문제를 해결하려고 하고 있기 때문에 벡터를 이용해서 풀어보고자 한다.

int n,m;
vector<int> v;
vector<bool> broke(10,false); //0~9 중에서 고장난 버튼 지정

 

n은 이동하고자하는 채널 번호,

m은 고장난 숫자 버튼의 개수이다.

 

벡터를 통해 고장난 버튼을 지정하자.

초기값은 false로 모두 맞추고, 입력 받은 후에는 true로 바꾸어 줄 것이다.

for(int i = 0; i < m; i++){
   int num;
   cin >> num;
   broke[num] = true;
}

 

현재 채널 100번에서 입력 받은 n번의 채널까지 얼만큼 차이가 나는지 확인하기 위해서 아래와 같은 코드를 작성할 수 있다.

int minnum = abs(100 - n);

 

abs()라는 함수인데, 이는 절대값을 구할 때 사용되는 함수이다.

• abs(x)는 x가 음수일 경우 양수로 변환하고, 양수면 그대로 반환한다.
• cmath 또는 cstdlib 헤더 파일에 포함되어 있지만, 기본적으로 사용 가능하다.

채널 번호는 999999 까지 가능하다고 했으니,

for (int i = 0; i <= 999999; i++)

 

모든 숫자를 하나씩 확인한다.

 

그리고 각 자리수를 검사하면서, 입력했던 고장난 버튼이 있는지 확인한다.

int tmp = i, len = 0;
bool isValid = true;

 

 

• tmp = i: 숫자를 복사하여 검사한다.
• len = 0: 해당 숫자를 입력하는 데 필요한 버튼 횟수를 저장한다.
• isValid = true: 해당 숫자가 숫자 버튼만으로 입력 가능한지 판별하는 변수를 설정한다.

0번 버튼이 고장났다면 건너뛰고, 

만약, 0번 채널로 갈 수 있다면 len = 1 로 만들어준다.

if (tmp == 0) { 
    if (broke[0]) {
        continue;
    }
    len = 1;
}

 

숫자 i 가 고장난 버튼을 포함하고 있는지를 확인한다.

while (tmp > 0) {
    if (broke[tmp % 10]) { 
        isValid = false;
        break;
    }
    tmp /= 10;
    len++;
}

 

tmp % 10 을 하는 이유는 가장 오른쪽 자리수를 확인하기 위함이다.

 

만약, 숫자 버튼을 통해서 채널 이동이 가능하다면

+ 혹은 - 버튼을 통해서 n번의 채널로 이동하는 횟수를 더해준다.

if (isValid) {
    int num = len + abs(n - i);
    minnum = min(minnum, num);
}

 

minnum 의 값을 갱신해주면서 최소로 입력해야하는 버튼 수를 구할 수 있다.

 

 

 

전체 코드

#include <iostream>
#include <vector>

//리모컨
using namespace std;

int main(){
    int n,m;
    vector<int> v;
    vector<bool> broke(10,false); //0~9 중에서 고장난 버튼 지정

    cin >> n;
    cin >> m;

    for(int i = 0; i < m; i++){
        int num;
        cin >> num;
        broke[num] = true;
    }
    //+ 랑 - 만 사용하는 경우
    int minnum = abs(100 - n);

    //숫자버튼을 이용한 모든 채널 탐색
    for(int  i = 0; i <= 999999; i++){
        int tmp = i, len = 0;
        bool isValid = true;

        if(tmp == 0){ //0 입력 시 예외
            if(broke[0]){
                continue;
            }
            len = 1;
        }
        while(tmp > 0){
            //고장난 버튼이 포함되는 경우
            if(broke[tmp % 10]){
                isValid = false;
                break;
            }
            tmp /= 10;
            len++;
        }
        if(isValid){
            int num = len+abs(n - i);
            minnum = min(minnum, num);
        }
    }
    cout << minnum << '\n';
}

 

 

골드5 난이도의 문제였다. 너무 어려웠다. 문제를 이해하는 것부터가 너무 버거웠다. 햄버거? ㅋㅋ 

현재 시간 오후 5시, 내가 문제를 풀기 시작한 시간 오전 9시.

물론~ 사이에 다른 것도 하고 밥도 먹었지만.. 너무 오래걸렸다.

알고리즘 스터디를 하고 있다. 거기서 매주 풀어야하는 문제를 지정해주는데...

이거 말고도 분명 다른 문제가 있는데..

이것만 하루종일 풀었다.

나 진짜 울어.

지금까지 여러 문제를 풀면서 내가 어떤 부분이 약한지 생각해봤는데, 크게 2개있다.

1. 문제 이해력 부족

2. 스스로 해결하려는 의지 부족

 

이것만 고치면 완벽하게 문제를 풀 수 있을 것 같은데,,, 쉽게 안 고쳐진다.

완전 기초적인 쉬운 문제(사칙연산)를 푸는 단계는 지난 것 같고,

실버 난이도 정도를 정말 내 힘으로 풀려는 노력을 해야겠다.

 

모두들 포기하지 마세요. 왜냐면 저도 포기 안 했거든요 ㅋㅋ

화이팅.

 

 

 

 

 

 

 

 

 

 

 

더 좋은 풀이가 있다면 댓글로 알려주세요 !!

피드백 환영입니다☺️