[백준] 1107.cpp : 리모컨

www.acmicpc.net/problem/1107

1107번: 리모컨

#include <iostream>
#include <string>
using namespace std;

string n;                       // 원하는 채널값을 string 으로 받음 (길이 재기 위해서)
int intN, m, ans = 500000;      // intN 이 n 을 정수로 바꾼 실제 값
bool buttons[10];               // 고장여부 정보

int abs(int a) { return a >= 0 ? a : -a; }  // 절댓값 반환

int check(int num)              // 완전탐색 함수
{
    int temp = num;             // 임시 변수 temp 는 해당 숫자가 고장 안 난 숫자들로 이루어졌는지 확인위해
    int digit = 0;              // 자릿수 저장
    while(true)
    {
        if(buttons[temp % 10]) return 1000000;      // 자리 하나씩 검사하면서 고장난 번호가 있으면 이상값 반환
        digit++;                                    // 해당 자리에 문제가 없으면 자릿수 1 증가시켜주고
        temp /= 10;                                 // 한자리 지움
        if(temp == 0) break;                        // 더 자리가 없으면 종료
    }
    return digit + abs(intN - num);                 // 해당 채널로 번호 누른 횟수 + 채널에서 목표값까지의 횟수 반환
}

int main(void)
{
    cin >> n >> m;
    for(int i = 0, data ; i < m ;i++)
    {
        cin >> data;
        buttons[data] = true;
    }
    for(int i = n.size() - 1, temp = 1 ; i >= 0 ; i--, temp *= 10)
    {
        intN += temp * (n[i] - '0');
    }
    int pure = abs(intN - 100);                                         // 100 부터 +- 로만 돌렸을 때의 횟수
    if(m == 0) cout << (pure > n.size() ? n.size() : pure) << '\n';     // 고장난게 없을 때 먼저 처리해주고
    else if(m == 10) cout << pure << '\n';                              // 모두 고장났을 때도 처리해준 다음
    else
    {
        for(int i = 0, temp ; i <= 1000000 ; i++)                       // 1 ~ 1000000 까지 모든 채널 완전탐색
        {
            temp = check(i);                                            // 해당 채널의 클릭횟수를 받아서
            if(temp < ans) ans = temp;                                  // 최솟값인지 확인
        }
        if(pure >= ans)  cout << ans << '\n';
        else cout << pure << '\n';
    }
}

 

[Approach]

1. 방법 5가지를 검사해서 최솟값을 찾기

     (100 부터 +- 로만 움직이기, 같은 자릿수에서 내려가기/올라가기, 하나 아랫자릿수에서 올라가기, 하나 윗자리수에서 내려가기)

     -> 검사를 진짜 꼼꼼하게 잘 해주면 통과할 것 같다. 그런데 이 방법은 아닌 것 같다. 지저분함의 극치

2. 최대 6자리이기 때문에 최대가 9^6 이면 10만개 이하다. 전부 다 검사도 가능해보인다.

 

[Point]

1. 문제 진짜 딱 내가 싫어하는 스타일. 어찌저찌 풀긴 했는데 그냥 기분이 더럽다

 

[More]

1. 재귀로는 못 푸는 줄 알았는데 어떻게 하신거지...(6669832) 이외에도 여러 분 계신다

2. DFS (9103052)

3. 시간 제한을 어떻게 계산하는지 - 빅오 계산 방법? 다른 것이 있나