BOJ 1107 - 리모컨

• 보고 싶은 채널 N(0<=N<=500000), 0-9 중 고장난 버튼이 주어질 때 리모컨을 몇 번 조작해야 원하는 채널을 틀 수 있는지 구하는 문제이다. 숫자 버튼 이외에 +, -버튼이 있어 숫자 버튼 10개가 고장날 경우도 주어지고, 원래 틀어져 있던 채널은 100번이다.

문제 풀이

• 작동 가능한 버튼을 조합해 만들 수 있는 수들을 정렬해서 lower_bound와 그 전 숫자를 틀고 +/- 조작과 100에서 +/-로 조작하는 방법의 회수 중 작은 것을 구했다.

• 바킹독 문제집을 풀기 전에 푼 적있어서 풀고나서 그때 푼 코드와 비교해봤다.

소스코드

#include<bits/stdc++.h>
using namespace std;
typedef vector<int> vi;

int getpow(int n, int p);
int getd(int p);
int chkvld(vi& p, int l);
int vtoi(vi& digits, vi& r);

int main()
{
	int n, b;
	cin>>n>>b;
	vi bb(b), r, v;
	for(int i=0;i<b;i++) cin>>bb[i];
	if(!bb.empty()) sort(bb.begin(), bb.end());
	b=0;
	for(int i=0;i<10;i++){
		if(b<bb.size() && i==bb[b]){
			b++;
			continue;
		}
		r.push_back(i);
	}
	if(r.empty()){
		cout<<abs(n-100);
		return 0;
	}
	int ndigit=getd(n);
	for(int i=1;i<ndigit+2;i++){
		vi digits(i, 0);
		//cout<<i<<endl;
		while(chkvld(digits, r.size())){
			v.push_back(vtoi(digits, r));
			digits[0]++;//0 : digit of 1
		}
		if(v.back()>n) break;
	}
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());
	int lb=lower_bound(v.begin(), v.end(), n)-v.begin();
	if(v[lb]==n) cout<<((ndigit<abs(n-100))?ndigit:abs(n-100));
	else{
		int l=987654321, r, ans=abs(n-100);
		if(lb!=0) l=abs(v[lb-1]-n);
		l+=getd(v[lb-1]);
		r=abs(v[lb]-n);
		r+=getd(v[lb]);
		if(l>r) l=r;
		cout<<((l<ans)?l:ans);
	}
}

int getpow(int n, int p){
	int r=1;
	while(p--) r*=n;
	return r;
}

int getd(int p){
	int r=0;
	if(p==0) return 1;
	while(getpow(10, r)<=p) r++;
	return r;
}

int chkvld(vi& p, int l){
	for(int i=0;i<p.size()-1;i++){
		if(p[i]==l){
			p[i]=0;
			p[i+1]++;
		}
	}
	if(p.back()==l) return 0;
	else return 1;
}

int vtoi(vi& digits, vi& r){
	int res=0;
	for(int i=0;i<digits.size();i++) res+=r[digits[i]]*getpow(10, i);
	return res;
}

전에 짰던 코드

#include<iostream>
#include<cstdio>
#include<string>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;

vector<int> m;
string s;
int calc(vector<int> indxs){
    int num=0;
    for(int i=0;i<indxs.size();i++){
        if(indxs[i]==-1) continue;
        num+=m[indxs[i]]*pow(10, indxs.size()-i-1);
    }
    return num;
}
int digits(int newnum){
    int i=1, cnt=0;
    if(newnum==0)
        return 1;
    for(i;i<=newnum;i*=10)
        cnt++;
    return cnt;
}
int main()
{
    int M, cnt, orgn=0;
    getline(cin, s);
    for(int i=0;i<s.length();i++)
        orgn+=(s.c_str()[i]-'0')*pow(10, s.length()-i-1);
    //orgn : N
    cnt=abs(orgn-100);//only by +/-
    scanf("%d", &M);
    for(int i=0;i<10;i++)
        m.push_back(i);
    for(int i=0;i<M;i++){
        int j;
        scanf("%d", &j);
        m.erase(find(m.begin(), m.end(), j));
    }
    //m : vector of possible number buttons
    if(m.size()==0){
        printf("%d", cnt);
        return 0;
    }
    
    int f=1;//search incompleted
    vector<int> indxs(6, -1), vcmp(6, m.size()-1);
    indxs[indxs.size()-1]=0;
    while(f){
        int newnum=calc(indxs), newcnt=abs(newnum-orgn)+digits(newnum);
        if(cnt>newcnt) cnt=newcnt;
        for(int i=indxs.size()-1;i>=0;i--){
            if(++indxs[i]==m.size()){
                indxs[i]=0;
                if(i==0)
                    f=0;
            }
            else break;
        }
    }
    printf("%d", cnt);
    return 0;
} 

풀고나서

• 전과 푸는 방법 자체는 동일했다. 근데 전에는 숫자를 조합할 때마다 조작 횟수를 계산해서 비교했고, 이번에는 N과 가장 가까운 두 값만 비교했다. 그리고 숫자를 조합하면서 조합하는 숫자가 N보다 커지면 종료되게 만들었다. 그 결과 실행 시간이 256ms, 56ms로 많이 차이가 났다.

• 이전 코드는 main에 다 박아넣어서 가독성이 별로였지만 이번에 짠 코드는 함수로 많이 빼서 보기 훨씬 좋았다.(최근에 짜서 그럴 수도 있을 것 같다.)

• 이런 완전 탐색 문제는 edge case가 많아서 반례 찾기가 정말 고된 것 같다.

• stream에 사용하는 «와 ternary operator ? 중 «가 우선순위가 더 높은지 처음 알았다.