C++ 백준 1107 리모컨

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

1107번: 리모컨

 

재귀 함수를 이용하여 문제를 해결하였다. 

 

[ 해결 ] 

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

int N = 0; //이동하고자 하는 채널 번호 (0 ≤ N ≤ 500,000)
int M = 0; //고장난 번호의 개수 (0 ≤ M ≤ 10)
int broken[10]={};
int start = 100; //초기 채널 번호 
int min_click = 987654321; //최소 값(결과)

void solve(string comp){
    for(int i=0; i<=9; i++){
    	//해당 버튼이 고장나지 않으면 입력해 본 후 최소 클릭 여부 판단 
        if(broken[i]==0){
            string tmp = comp+to_string(i);
            min_click = min(min_click, abs(N-stoi(tmp))+(int)tmp.length());
            // 총 길이가 6보다 작으면 재귀 
            if(tmp.length()<6){
                solve(tmp);
            }
        }
    }
}

int main(void){
    //N입력 -> 최소값 초기화 
    cin>>N;
    min_click = abs(N-start);
    
    //M 입력 
    cin>>M;

    //broken Button - normal[0] broken[1]
    for(int i=0; i<M; i++){
        int brokenButton = -1;
        cin>>brokenButton;
        broken[brokenButton]=1;
    }

    solve("");
    cout<<min_click;
    return 0;
}

 

 

[ 실패했던 코드 ] 

이동하고자 하는 채널의 문자열 길이를 계산해 그 길이와, 길이+1 만큼만 재귀를 돌린 게 문제였다. 예제는 다 돌아가길래 뭐가 문젠지 찾는 데 애먹음...ㅎ,,,

#include <iostream>
#include <string>

using namespace std;
int N = 0; //이동하고자 하는 채널 번호 (0 ≤ N ≤ 500,000)
int M = 0; //고장난 번호의 개수 (0 ≤ M ≤ 10)
int broken[10]={};
int start = 100; //초기 채널 번호 
int min_click = 987654321; //최소 값(결과)
int cnt = 0;

void recursive(int cnt_rcsv, string comp){
    if(cnt_rcsv>cnt+1){ return; }
    else{
        for(int i=0; i<=9; i++){
            string tmp = "";
            if(broken[i]==0){
                tmp = comp+to_string(i);
                min_click = min(min_click, abs(stoi(tmp) - N)+cnt);
                recursive(cnt_rcsv+1, tmp);
            }
        }
    }
}

int main(void){
    //N입력 -> 최소값 초기화 
    cin>>N;
    min_click = abs(N-start);
    
    //M 입력 
    cin>>M;

    //broken Button - normal[0] broken[1]
    for(int i=0; i<M; i++){
        int brokenButton = -1;
        cin>>brokenButton;
        broken[brokenButton]=1;
    }

    //N 자릿수 계산 
    int tmp = N;
    while(tmp>0){
        tmp=tmp/10;
        cnt++;
    }

    recursive(0, "");
    cout<<min_click;
}