백준 1107번-리모컨

문제

수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다.

리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다.

수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오. 

수빈이가 지금 보고 있는 채널은 100번이다.

입력

첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다.  둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주어지며, 같은 버튼이 여러 번 주어지는 경우는 없다.

출력

첫째 줄에 채널 N으로 이동하기 위해 버튼을 최소 몇 번 눌러야 하는지를 출력한다.

 

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<numeric>
#include<math.h>
using namespace std;


void cho(int deep,vector<int> nam,int H_sum,vector<int> &nam2) {
	int sum = 0;
	for (int i = 0; i < nam.size(); i++) {
		sum = H_sum + nam[i] * pow(10, deep-1);
			if (deep < 1) {
				return ;
			}
			else { cho(deep - 1, nam, sum,nam2); }
			if(deep==1)
			nam2.push_back(sum);
	}

}

int main() {
	int N,del,del_value,min_cnt=500000,N_size,num;
	cin >> N>>del;
	N_size = to_string(N).length();
	vector<int> nam = { 0,1,2,3,4,5,6,7,8,9 };
	vector<int> mid_nam;
	vector<int> top_nam;
	vector<int> bot_nam;
	int min_mid = abs(N - 100), min_top = 500000, min_bot = 500000;
	vector<int>::iterator iter;
	for (int i = 0; i < del; i++) {
		cin >> del_value;
		iter=find(nam.begin(), nam.end(), del_value);
		nam.erase(iter);
	}


		cho(N_size, nam, 0, mid_nam);
		cho(N_size + 1, nam, 0, top_nam);
		cho(N_size - 1, nam, 0, bot_nam);

		for (auto i : mid_nam) {
			num = abs(N - i) + N_size;
			if (num < min_mid)
				min_mid = num;
		}
		for (auto i : top_nam) {
			num = abs(N - i) + N_size + 1;
			if (num < min_top)
				min_top = num;
		}
		for (auto i : bot_nam) {
			num = abs(N - i) + N_size - 1;
			if (num < min_bot)
				min_bot = num;
		}
		int out1 = min(min_mid, min_top);
		int out2 = min(out1, min_bot);
		cout << out2;
	
}

정말 재귀함수로 만드느라 힘들었다. 기본적으로 main에서는 입력들을 받고 0~9가 있는 벡터에서 삭제할 부분들을 삭제해주고 계산하게 된다.

min_mid의 초깃값이 abs(N-100)인 이유는 10개의 버튼이 망가졌거나 버튼0만 남거나 100채널에 근접한 수라  +나 -로 계산을 해야할때를 기본값으로 줘서 처리했다.

cho 가 mid,top,bot으로 나뉜 이유는 99999에 근접한수가 100000 인것처럼 자릿수보다 +-1을 한 경우도 계산해 준다.

cho부분은 채널로 이동해서 나머지부분을 +-을 하기때문에 기본채널 100과 관련이 없다(그래서 abs(N-i)+N_size를 해주고 +-1을 해준것이다.)

그 후 가장 작은 값을 출력함으로 끝.

 

cho함수 같은 경우에는 자릿수를 기준(deep)으로 N이 6자릿수 라면 총 6자리로 입력이 된다.(ex 111111,222222)

nam벡터는 정상적인 버튼의 모음 H_sum은 상위 함수의 sum값을 저장한다.

vector &nam2는 call by reference로 각각 mid_nam,top_nam_bot_nam에 저장하기 위해 존재한다.

재귀함수를 간단하게 정리해보면 남은 버튼으로 해당 자릿수만큼 모든 경우의 수를 벡터에 저장하게 하는 함수이다.(ex) 남은 버튼 1,5 N의 자릿수3이면)

111
115
151
155
511
515
551
555