[BOJ]1107번: 리모컨(c++)

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

1107번: 리모컨

 

 

방법 1: 브루트 포스

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int possible(int N, bool is_broken[])
{
    int len = 0;
    do
    {
        if (is_broken[N % 10])
        {
            return 0;
        }
        len++;
        N /= 10;
    } while (N);
 
    return len;
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    const int NOW = 100;
    const int MAX = 1'000'000;
 
    // 입력
    int N, M;
    cin >> N >> M;
    bool is_broken[10] = { 0, };
    
    for (int i = 0; i < M; i++)
    {
        int tmp;
        cin >> tmp;
        is_broken[tmp] = true;
    }
 
    // 현재 채널에서 +/- 버튼만으로 이동하는 횟수
    int cnt = abs(N - NOW);
 
    for (int i = 0; i <= MAX; i++)
    {
        // i를 이루는 숫자 중 고장난 버튼이 없으면, 숫자길이 반환
        int len = possible(i, is_broken);
        if (len)
        {
            // 버튼 누르는 횟수가 더 작으면
            if (cnt > abs(N - i) + len)
            {
                cnt = abs(N - i) + len;
            }
        }
    }
 
    cout << cnt;
 
    return 0;
}

 

방법 2: DFS. 하지만 런타임 에러...

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
 
using namespace std;
 
int N;
int cnt;
 
void perm(const string& numbers, string output, int depth, int r)
{
    if (depth == r)
    {
        // 목표 채널보다 1자리 적은 수 ~ 1자리 많은 수 체크
        for (int i = 0; i < 3; i++)
        {
            if (r - i >= 0)
            {
                int res = stoi(output.substr(0, r - i));
                
                // 버튼 누른 총 횟수 : 가장 가까운 채널 길이 + (+/-) 버튼 누른 횟수
                if (cnt > abs(res - N) + to_string(res).size())
                {
                    cnt = abs(res - N) + to_string(res).size();
                }
            }
        }
 
        return;
    }
 
    for (int i = 0; i < numbers.size(); i++)
    {
        perm(numbers, output + numbers[i], depth + 1, r);
    }
}
 
int broken_cnt(int N, bool is_broken[])
{
    int cnt = 0;
    do
    {
        if (is_broken[N % 10])
        {
            cnt++;
        }
        N /= 10;
    } while (N);
    return cnt;
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    const int now = 100;
 
    // 입력
    int M;
    cin >> N >> M;
    bool is_broken[10] = { 0, };
 
    for (int i = 0; i < M; i++)
    {
        int tmp;
        cin >> tmp;
        is_broken[tmp] = true;
    }
 
    // 목표 채널이 현재 채널이거나, 모든 숫자버튼이 고장났을 때
    if (abs(N - now) == 0 || M == 10)
    {
        cout << abs(N - now);
        return 0;
    }
    // 만들려는 채널 숫자에 해당하는 고장난 버튼이 없을때
    if (broken_cnt(N, is_broken) == 0)
    {
        cout << min((int)to_string(N).size(), abs(N - now));
        return 0;
    }
 
    // 정상 버튼 문자열 만들기
    string numbers;
    for (int i = 0; i < 10; i++)
    {
        if (!is_broken[i])
        {
            numbers.push_back((char)i + '0');
        }
    }
 
    // 정상버튼으로 목표채널과 가장 가까운 채널 만들기
    cnt = abs(N - now);
    
    perm(numbers, "", 0, to_string(N).size() + 1);
 
    cout << cnt;
 
    return 0;
}

 

 

유독 질문글에서 "리모컨 부숴버리고 싶네요ㅜㅜ"라는 글이 많았다.

나도 동감합니다...

브루트 포스로 풀면 쉽게 풀리는 문제였지만,

어떻게든 DFS로 해보려는 나의 2일간의 시간은 큰 교훈을 남기고 떠났다.

 

 

TIP1

브루트 포스 for문으로 푸시오..

목표 채널 범위가 500,000까지라서, 2배 해도 1,000,000 까지 밖에 안됨.

 

이문제는 BFS로 풀면 안되는 문제다. 

이유 1)  버튼의 중복 사용이 가능하기 때문에, 가짓수가 너무 많아진다.

이유 2)  목표 채널 자릿수보다 1자리 적은수 ~ 1자리 많은 수 

이렇게 총 3가지 케이스를 다 조합해야 한다.

 

위에 올린 소스코드도

게시판에 존재하는 모든 테스트 케이스를 돌려보면 다 맞게 나온다.

다만 좀 늦게 나온다...ㅋㅋ

특히 정상버튼이 7~8개쯤 되고 목표 채널이 5~6자리 일때.

BOJ 채점을 돌려도 중간에 런타임 때문에 끝나버린다.  

 

 

 

TIP2

최대값을 문제에서 목표하는 채널의 2배로 잡자.

문제: 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 

 

예제3)
500000
8
0 2 3 4 6 7 8 9

이유가 3번째 예시에서 특히 잘 드러나는데,

155555 보다는 511111에서 내려가는게 더 버튼 누르는 횟수가 적기 때문에!

목표 채널보다 더 큰 값까지 확인해주어야 한다. 

 

 

TIP3

브루트포스의 기본... 그냥 0부터 최대값까지 다 확인하자.

기본값은 +/- 만으로 목표채널까지 가는 횟수.

 

비교할때부터 총 버튼 누르는 횟수를 가지고 비교하는게 좋다.