[완전 탐색] 백준 문제 풀이 - 1107 리모컨

👩🏻‍💻 문제링크

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

1107번: 리모컨

 

✍️ 아이디어 (처음에 잘못 접근함)

1. 문제 이해

• 처음엔 사용할수 있는 버튼을 가지고 모든 수의 조합을 만들려고 했는데 브루트포스는 그냥 모든 수(0~1000000)을 다 해보면 되는거였다

2. 0~1000000의 수를 다 해보면서..

   1. 이 채널에 고장난 버튼이 없는지

   2. 누를수 있다면 목표 버튼이랑 최소차이가 나는지 확인

3. 고장난 버튼을 체크할때 2가지 방법이 있음

   1. 숫자를 문자열로 바꿔서 인덱스로 각자리수가 고장난 버튼인지 비교

   2. 숫자를 %10으로 1의자리 고장난 버튼인지 확인하고 /=10 으로 한자리씩 땡기기

✍️소스코드

• 강의를 참고하고 고친 나의 코드

#include <iostream>
#include <algorithm>
using namespace std;
bool broke[10];

bool possible(int x) //x라는 수가 버튼으로 누를수 있는지 없는지 판별
{
	if(x==0) return !broke[0];
	while(x>0)
	{
		if(broke[x%10]==true)
			return false;
		else
			x/=10;
	}
	return true;
}

int lengths(int x) //x라는 수의 자릿수를 판별
{
	if(x==0) return 1;
	int ans = 0;
	while(x>0)
	{
		x/=10;
		ans++;
	}
	return ans;
}

int main()
{
	int n; cin>>n;
	int m; cin>>m;
	int result = abs(n-100);
	for(int i=0; i<m; i++)
	{
		int x; cin>>x;
		broke[x]=true;
	}
	for(int i=0; i<=1000000; i++)
    //1000000까지인 이유?  => 문제에서 이동하려고 하는 채널 N의 범위가 0 ~ 500000 이지만,
    //이동하려는 채널보다 높은 위치에 있을 때 감소하는 범위도 고려해야 하므로..
	{
		if(possible(i)) //i가 리모컨 버튼으로 누를수 있으면..
		{
			int length = lengths(i);
			if(result>abs(i-n)+length)
			{
				result=abs(i-n)+length; //++ -- 갯수랑 자릿수를 더한것
			}
		}
	}
	if(abs(n-100) <= 3)
	{
		result=abs(n-100);
	}
	cout<<result<<'\n';
}

 

• 다른 사람의 코드 (이 숫자가 버튼 고장난것이 없는지 확인 할때 int를 string으로 고쳐서 확인함)

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cmath>

using namespace std;


vector<int> dp;
vector<bool> mal(10,false);

bool check(int now){ //now라는 숫자를 누를때 고장난 버튼이 없는지 체크 

    string s = to_string(now); 숫자를 string으로 바꿈
    for(int i = 0; i <s.length();i++){
        if(mal[s[i]-48]){
            return false;
        }

    }

    return true;

}



int main(){

    int n,c;
    cin>>n>>c;

    int tmp;

    for(int i = 0; i < c; i++){
        cin>>tmp;
        mal[tmp] = true;
    }


    string st = to_string(n);

    int minimum = abs(n-100);
    for(int i = 0; i <= 1000000; i++){
        if(check(i)){
            int tmp = abs(n-i)+to_string(i).length();
            minimum = min(minimum,tmp);
        }

    }


    cout<<minimum<<endl;


    return 0;
}

 

체감난이도	걸린시간	참고	사용 문법
상	1hour	강의 참고	완전 탐색(그냥 해보기)