[C++] 리모컨

백준 1107번

 

dfs로 문자열을 열심히 만들다가 뭔가 이상하다는 느낌이 들어서 방법을 고쳤다

처음 생각한 방법은 문제에 있는 예시처럼 5457이면 먼저 5를 쓸수 있는지 확인해서 5, 그다음 54, 545, 5455 이런식으로 문자열을 늘려갔다

하지만 999와 같은 경우는 1000 - 1이 유리한데 내 방식은 찾지 못할 것 같았다

예외 처리를 해주기에는 이런 상황이 너무 많을 수 있다는 생각이 들어 제한 조건을 다시 살펴보았다

 

채널은 총 500000개이고 한 문자열을 만들 수 있는지 없는지 확인하는데에는 최대 6밖에 들지 않았다

따라서 만들 수 있는 전체 문자열을 확인하는것이 예외처리도 없고 간편하겠다는 생각이 들었다

다만 입력으로 들어오는 채널은 500000이하이지만 500001 - 1 이런식으로 만들 수도 있으므로 필요한 최대값인 1000000 으로 검사 범위를 늘려주었다

 

#include <iostream>
#include <string>
 
using namespace std;
 
int broken[10];
int ans;
 
int can_make(string str){
    int len = str.length();
    for(int i = 0 ; i < len ; i++) {
        if(broken[str[i]-'0']) return 0;
    }
    //cout << str << endl;
    return 1;
}
 
int main(){
    string N;
    int M;
    cin >> N >> M;
    for(int i = 0; i < M ; i++) {
        int number;
        cin >> number;
        broken[number] = 1;
    }
    int len = N.length();
    string res = "";
    ans = abs(stoi(N)-100);
    for(int i = 0 ; i <= 1000000 ; i++){
        string str = to_string(i);
        if(can_make(str)){
            int cnt = abs(stoi(N)-stoi(str));
            cnt += str.length();
            if(ans>cnt) ans = cnt;
        }
    }
    cout << ans << endl;
}

 

먼저 현재 채널인 100번에서 +,-만 이용해서 이동한 경우를 ans에 넣어주었다

그 다음 만들 수 있는 모든 문자열을 만들어 해당 위치에서 +,-를 몇번 이용해야 하는지 체크하였다

이 때 문자열을 만들어 사용하는 경우는 문자열을 만들 때 버튼을 눌러야 해서 문자열 길이만큼 추가로 더해주었다

 

중간에 방법을 바꾸었던게 좋은 시도였던 것 같다

안바꾸었다면 문자열 예외처리하느라 고통받았을 듯ㅠㅠ

전체를 돌지 않고 찾아야하는 채널에서 번호가 큰 가장 가까운 채널, 번호가 작은 가장 가까운 채널을 확인한다면 반복문을 더 작게 쓸 수 있을 것 같다