백준 1107 - 리모컨

문제 링크

생각과 접근

• 리모콘은 같은 숫자를 여러 번 누를 수 있는, 중복순열의 형태이다. 중복순열을 구현할 수 있다면 쉽게 풀 수 있는 문제였다.
• 고장난 리모콘 버튼을 통해서 살아있는 리모콘 숫자를 기억하는 vector<int> live;를 선언했다.
• 우선, answer의 초깃값을 answer = abs(target - START);로 잡아두었다. 단순히 +와 - 키로 얻을 수 있는 리모콘 클릭 수로 초기화한 것이다.
• 채널의 범위가 0 <= N <= 500000이므로, 1개부터 6개까지 고를 수 있는 중복순열을 구현해 기존의 answer와 비교해서, 더 작은 값으로 update하면 되겠다.

    void dfs(int cnt, int tar){
        if(cnt == tar){
            temp = 0;
            for(int i = 0; i < cnt; i++){
                temp *= 10;
                temp += cand[i];
            }
            answer = min(answer, tar + abs(target - temp));
        }
        else{
            // 중복순열을 하는 코드
            // vector live를 전부 돌면서 그냥 넣으면 된다. 왜? 버튼을 누르는 수는 제한이 없으니까!
            for(int i = 0; i < live.size(); i++){
                cand[cnt] = live[i];
                dfs(cnt + 1, tar);
            }
        }
    }

코드

#include <bits/stdc++.h>
#define START 100
using namespace std;

int target, brokenNum, temp, answer;
vector<int> tmp(10, 0);
vector<int> live;
vector<int> cand(6, 0);

void dfs(int cnt, int tar){
    if(cnt == tar){
        temp = 0;
        for(int i = 0; i < cnt; i++){
            temp *= 10;
            temp += cand[i];
        }
        answer = min(answer, tar + abs(target - temp));
    }
    else{
        for(int i = 0; i < live.size(); i++){
            cand[cnt] = live[i];
            dfs(cnt + 1, tar);
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);

    cin >> target >> brokenNum;
    for(int i = 0; i < brokenNum; i++){
        cin >> temp;
        tmp[temp] = 1;
    }
    for(int i = 0; i <= 9; i++){
        if(tmp[i] == 0)
            live.push_back(i);
    }

    answer = abs(target - START);

    for(int i = 1; i <= 6; i++){
        for(int j = 0; j < 6; j++){
            cand[j] = 0;
        }
        dfs(0, i);
    }

    cout << answer;
}

채점 결과