[BOJ/백준] 1107 리모컨

● [문제번호 1107] 리모컨

https://www.acmicpc.net/problem/1107

1107번: 리모컨

 

● 알아야 할 것

: 브루트 포스 (Brute Force)

 

● 풀이 과정

: 목표 채널로 이동하는 방법

1. +, - 로만 이동하는 경우

→ 목표 채널 - 현재 채널(100)

 

2. 숫자 버튼을 이용해 채널 이동 후 +, - 로 이동하는 경우

어떤 채널로 이동해야 할까 → (고장나지 않은 숫자 버튼으로 갈 수 있는) (목표 채널과 가장 가까운) 채널

 

목표채널을 기준으로 양방향으로 gap만큼 떨어져있는 채널을

고장나지 않은 숫자 버튼으로 갈 수 있는지 확인한다.

그 다음 gap만큼 +, - 로 이동하면 된다.

 

● 주의 할 것

: 최대 채널은 무한대이지만, 최소 채널을 0이다.

따라서 0채널을 고장나지 않은 숫자 버튼으로 갈 수 있는 지 확인할 때 주의하여 예외처리한다.

 

: 만약 목표 채널로 부터 가장 가까운 채널이 양방향에 있다면,

자릿수에 의해 차이가 날 수 있기 때문에

작은 숫자의 채널을 선택해야한다.

 

: 0의 숫자 길이는 0이므로 예외처리가 필요하다.

 

● 참고 할 것

: NULL

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

bool remote[10] = {false, };
int N, M, Ngap, gap;

// 채널 길이 구하기
int numlen(int num)
{
    // 0 채널인 경우
    if(num == 0)
        return 1;
    
    int len = 0;
    while(num > 0)
    {
        len++;
        num /= 10;
    }
    return len;
}

// 리모컨 숫자만으로 갈 수 있는 채널인지 확인
bool check(int num)
{
    // 0채널로 가려는 경우
    if(num == 0)
    {
        if(remote[0])
            return false;
        return true;
    }
    
    while(num > 0)
    {
        if(remote[num % 10])
            return false;
        
        num /= 10;
    }
    return true;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> N >> M;
    
    // 고장난 버튼 입력
    for(int m = 0; m < M; m++)
    {
        int broken;
        cin >> broken;
        remote[broken] = true;
    }
    
    // 목표 채널 기준으로 gap만큼 떨어진 채널 확인
    for(gap = 0; gap <= 500000; gap++)
    {
        int temp1 = -1;
        int temp2 = -1;
        
        // 목표 채널 기준 작은 쪽
        if(N - gap >= 0 && check(N - gap))
            temp1 = N - gap;
        
        // 목표 채널 기준 큰 쪽
        if(check(N + gap))
            temp2 = N + gap;
        
        // 작은 쪽에서 가능한 경우
        // 작은 쪽, 큰 쪽 모두 가능하다면 작은 쪽 선택
        // (채널 길이가 짧을 가능성)
        if(temp1 != -1)
        {
            Ngap = temp1;
            break;
        }
        // 큰 쪽에서 가능한 경우
        // (이 경우는 큰 쪽만 가능한 경우에 실행됨)
        else if(temp2 != -1)
        {
            Ngap = temp2;
            break;
        }
    }
    
    // {+, - 로만 가는 경우} 와 {채널이동 후 +, - 로 가는 경우}
    cout << min(abs(N - 100), numlen(Ngap) + gap);

    return 0;
}

 

 

● [백준] - [알고리즘 기초 2/2] - [500 - 브루트 포스] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	2309	일곱 난쟁이	https://pirateturtle.tistory.com/228
2	3085	사탕 게임	https://pirateturtle.tistory.com/229
3	1476	날짜 계산	https://pirateturtle.tistory.com/230
4	1107	리모컨	https://pirateturtle.tistory.com/231
5	14500	테트로미노	https://pirateturtle.tistory.com/232
6	6064	카잉 달력	https://pirateturtle.tistory.com/233
7	1748	수 이어 쓰기 1	https://pirateturtle.tistory.com/234
8	9095	1, 2, 3 더하기	https://pirateturtle.tistory.com/235