백준 (1107) 리모컨

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

1107번: 리모컨

로직

2가지 경우의 수를 구해야 한다.

1. 100 에서 n의 값을 뺀 절대값

2. DFS를 사용하여 고장난 리모컨 채널을 제외환 모든 채널의 경우의 수를 만들면서 n과 모든 채널의 값을 뺀 절대값

 

1번과 2번의 최소 절대값을 비교하여 작은 수가 정답이 된다.

소스

#include <iostream>
#include<stdio.h>

using namespace std;

int n;
int nSize;
int resCnt;
int hres;
int minn = 10000000;
int used[10];
int flag = 0;

// n이 몇자리인지 구하는 함수
int getSize(int n){
	int cnt = 0;
	while (1){
		if (n <= 0){
			break;
		}
		n = n / 10;
		++cnt;
	}
	return cnt;
}

// rcnt는 채널의 자리수를 나타내며 res는 채널의 번호

void dfs(int res, int rcnt){
	if (rcnt > nSize+1){
    // 현재 채널이 1000이고 n이 999일때 자리수 까지만 가서 반환한다면
    // 1000 - 1 = 999인 경우는 탐색하지 못하므로 +1한 자리수까지 포함시킨다.
		return;
	}
	if (rcnt > 0){
		if (n != res){
			int sum = abs(n - res);
			resCnt = rcnt + sum;
			if (minn > resCnt) minn = resCnt;
		}
		if (n == res){
			resCnt = rcnt;
			if (minn > resCnt) minn = resCnt;
		}
	}

	for (int i = 0; i < 10; ++i){
		if (used[i] == 0){
			dfs(res * 10 + i, rcnt + 1);
		}
	}
}


int main(){
	freopen_s(new FILE*, "tes.text", "r", stdin);
	cin >> n;
	int ncnt;
	cin >> ncnt;
	for (int i = 0; i < ncnt; ++i){
		int idx;
		cin >> idx;
		used[idx] = 1;
	}
	if (n == 100){
		printf("0");
		return 0;
	}
	else{
		hres = abs(n - 100);
	}
	nSize = getSize(n);
	dfs(0, 0);

	if (minn > hres){
		printf("%d", hres);
	}
	else{
		printf("%d", minn);
	}


}