1107 ๋ฆฌ๋ชจ์ปจ

์•Œ๊ณ ๋ฆฌ์ฆ˜(๋ธŒ๋ฃจํŠธ ํฌ์Šค)

1. 0~100๋งŒ๊นŒ์ง€ ํ•˜๋‚˜์”ฉ ์˜ฌ๋ผ๊ฐ€๋ฉฐ, ๋˜๋Š”์ง€ ๊ฒ€์‚ฌํ•˜๊ณ , ๊ฐ€์žฅ ์ ๊ฒŒ ๋ˆ„๋ฅด๋Š” ๊ฑด์ง€ ์ €์žฅ
2. ๋˜๋Š”์ง€ ๊ฒ€์‚ฌํ•  ๋•Œ๋Š”, ๊ณ ์žฅ๋‚œ ๋ฒ„ํŠผ์„ bool ๋ฐฐ์—ด์— ์ €์žฅํ•˜์—ฌ ๋ฐ”๋กœ๋ฐ”๋กœ ์ฐธ์กฐ๊ฐ€๋Šฅํ•˜๊ฒŒ ํ•˜๊ณ , ๋’ค์—์„œ๋ถ€ํ„ฐ ํ•˜๋‚˜์”ฉ ๊ฒ€์‚ฌํ•˜์ž

ํ—›๋ฐœ์งˆ ๊ธฐ๋ก

1. ์ฒ˜์Œ์—” ๋“ค์–ด์˜จ ๋ฒ„ํŠผ์˜ ์ž๋ฆฟ์ˆ˜์— ๋งž๊ฒŒ, ๋ชจ๋“  ์ˆซ์ž๋ฅผ ๊ฒ€์‚ฌํ•˜๋˜ ์žฌ๊ท€๋กœ ์ˆ˜๋ฅผ ํ•˜๋‚˜์”ฉ ์ฑ„์›Œํ•˜๋Š” ์‹์œผ๋กœ ํ•˜์—ฌ ์•ˆ๋˜๋Š” ๊ฑด ๋ฏธ๋ฆฌ ์ œ๊ฑฐํ•˜๋Š” ์‹์œผ๋กœ ํ•จ
	-> ex) 2528์ด๋ฉด ๋ชจ๋“  4์ž๋ฆฌ์ˆ˜๋ฅผ ๊ฒ€์‚ฌํ•˜๋˜, ์•ž์—์„œ๋ถ€ํ„ฐ ์•ˆ๋˜๋Š”๊ฑด ๋ฐฐ์ œํ•˜๋ฉฐ ์ฑ„์›Œ๊ฐ
2. ๊ทธ๋Ÿฌ๋‚˜ ์ž๋ฆฟ์ˆ˜๋ฅผ ๋” ํฌ๊ฒŒ ํ•ด๋„ ์ตœ์†Œ๊ฐ€ ๋  ๊ฒฝ์šฐ๊ฐ€ ์กด์žฌ. ๋”ฐ๋ผ์„œ ์ž๋ฆฟ์ˆ˜๋ฅผ ๊ฝ‰์ฑ„์›Œ์„œ ๋ชจ๋“  ์ˆ˜๋ฅผ ๊ฒ€์‚ฌํ•˜์˜€์œผ๋‚˜ ์„ค๊ณ„์— ์–ด๋ ค์›€์„ ๋А๋‚Œ

์ฝ”๋“œ

#include <iostream>
#include <cstring>
#include <cmath>
 
using namespace std;
 
int to;
bool isable[10];
 
int pushButton();
int check(int cur);
int min(int a, int b) {
	return a < b ? a : b;
}
 
int main() {
	cin >> to;
 
	int n, t;
	cin >> n;
	memset(isable, 1, sizeof(isable));
	for (int i = 0; i < n; i++) {
		cin >> t;
		isable[t] = false;
	}
 
	cout << min(abs(100 - to), pushButton());
}
 
 
int pushButton() {
	int result = 2000000000, end = to * 10;
 
	for (int i = 0; i <= end; i++) {
		int length = check(i);
		if(length != -1)
			result = min(result, abs(to - i) + length);
	}
 
	return result;
}
 
int check(int cur) {
	int t = 10, index = 0, end = cur * 10;
 
	if (end == 0)
		end = 10;
 
	while (t <= end) {
		int c = cur % t;
		c = c / (t / 10);
 
		if (!isable[c])
			return -1;
 
		t *= 10;
		index++;
	}
 
	return index;
}