백준 1107. 리모컨 [실패]

1.실패 원인

너무 어려웠다. 일단 감이 전혀 안잡혔었고.. 다른 코드들과 비교했을 때 시작지점부터 차이가 났던것들이 있다. 첫 번째는 두가지 조건을 비교해야 했던 것. 100에서 시작해 +,-를 하는 횟수와 100이 아닌 수에서 +-를 하는 횟수중 최소값을 찾아야 한다는 조건 자체를 생각못했다. 두 번째는 각 자리수를 하나씩 비교하고 앉았었는데, 그렇게 하는 것이 아니라 특정 숫자를 입력값으로 주고 그 값이 가능한 값(리모컨 버튼이 고장나지 않은 값으로만 이루어져 있는 값)인지를 판별 하는 것이었다는 것. 즉, 완전탐색을 완전탐색 답게 풀려고 하지 않은 것이다. 

 

완탐은 보통 노가다인 경우가 허다한데 그래서 좀 얕잡아 보다가 털린 것 같다. 아직 선별된 문제중엔 첫 번째 문제라 타격이 크지 않지만.. 좀더 깊이 고민해서 풀어봐야겠다.

 

2.작성 코드

#include<iostream>
#include<string>
#include<algorithm>
 
using namespace std;
 
int broken[10];
 
bool possible(int k) {
    if (k == 0)
        return broken[0] ? false : true;
    while (k) {
        if (broken[k % 10] == 1) {
            return false;
        }
        k /= 10;
    }
    
    return true;
}
 
int find(const int& N) {
    int ret = abs(N - 100);
    int temp;
    int INF = N * 2 - 100;
    if (INF < 100)
        INF = 100;
    //0 ~ (N*2 - 100)의 범위의 번호를 리모컨으로 누르는 경우의 값을 구하자.
    for (int i = 0; i <= INF; i++) {
        //버튼을 누른 횟수
        temp = to_string(i).length() + abs(i-N);
        if (possible(i)) {
            //만일 이번 계산이 최소였다면, 저장하자.
            ret = min(temp, ret);
        }
    }
 
    return ret;
}
 
int main(void)
{
    int N, M, temp;
    cin >> N >> M;
    for (int i = 0; i < M; i++)
    {
        cin >> temp;
        broken[temp] = 1;
    }
    cout << find(N) << endl;
    return 0;
}

3.참고 코드

https://kyunstudio.tistory.com/94

[C++] 백준 1107 - 리모컨(brute force)

 

4. 해결 방안

어떻게보면 가장 접근이 쉬운 알고리즘 유형이긴하다. 왜냐하면 딱히 다른 스킬들이 필요한게 아니라 컴퓨터의 연산능력을 믿고 반복문으로 풀 수있기 때문이다. 그렇기에 코테에서 나오기도 쉽고 문제를 꼬아 내기도 쉬운 것같다.. 

브루트 포스가 무작정 풀기니 연습도 무작정 풀면(?) 나아질 것이라 생각이 든다.

 

예전에 plzrun님 블로그를 보고 문제를 선별하기 전에 브루트 포스 문제를 몇몇 풀어 봤다. 숫자 야구,자판기, nypc 문제등.. 그 때 몇가지 몰랐던 점들이 있었는데, string<->int 변환 (단순 변환을 얘기하는게 아니라 각 자리 수를 알아야 한다면 string으로 받고 index 접근후 '0'을 빼주는 연산을 하면 쉽게 구할 수 있다는 것) 같은 단순하지만 계속 나오는 기술들을 볼 수 있었다는 것. 스트링 문제 같은 경우에는 카카오톡 인턴 문제에서 심심치않게 나왔기에 관련 기술들을 연마할 필요가 있을 것 같다.