Algorithm/๋ฌธ์ œํ’€์ด

[๋ฐฑ์ค€] 1107๋ฒˆ - ๋ฆฌ๋ชจ์ปจ (C++)

moaoh 2023. 9. 2. 23:34

 

24039๋ฒˆ: 2021์€ ๋ฌด์—‡์ด ํŠน๋ณ„ํ• ๊นŒ?

๋ฐฑ์ค€ ์˜จ๋ผ์ธ ์ €์ง€์˜ ์†ก๋…„๋Œ€ํšŒ Good Bye BOJ, 2021!์˜ ๊ฐœ์ตœ์ผ์€ 2021๋…„ 12์›” 31์ผ์ด๋‹ค. ์›์ด๋Š” ๋Œ€ํšŒ๊ฐ€ ๊ฐœ์ตœ๋œ๋‹ค๋Š” ์‚ฌ์‹ค์ด ๊ธฐ๋ป ์ œ๋ชฉ์„ ๋šซ์–ด์ ธ๋ผ ๋ณด๋‹ค๊ฐ€ 2021์ด ๋ฌด์–ธ๊ฐ€ ํŠน๋ณ„ํ•˜๋‹ค๋Š” ์‚ฌ์‹ค์„ ๊นจ๋‹ฌ์•˜๋‹ค. ๊ทธ๋ ‡

www.acmicpc.net

๋ฌธ์ œ

์ˆ˜๋นˆ์ด๋Š” TV๋ฅผ ๋ณด๊ณ  ์žˆ๋‹ค. ์ˆ˜๋นˆ์ด๋Š” ์ฑ„๋„์„ ๋Œ๋ฆฌ๋ ค๊ณ  ํ–ˆ์ง€๋งŒ, ๋ฒ„ํŠผ์„ ๋„ˆ๋ฌด ์„ธ๊ฒŒ ๋ˆ„๋ฅด๋Š” ๋ฐ”๋žŒ์—, ์ผ๋ถ€ ์ˆซ์ž ๋ฒ„ํŠผ์ด ๊ณ ์žฅ๋‚ฌ๋‹ค.

๋ฆฌ๋ชจ์ปจ์—๋Š” ๋ฒ„ํŠผ์ด 0๋ถ€ํ„ฐ 9๊นŒ์ง€ ์ˆซ์ž, +์™€ -๊ฐ€ ์žˆ๋‹ค. +๋ฅผ ๋ˆ„๋ฅด๋ฉด ํ˜„์žฌ ๋ณด๊ณ ์žˆ๋Š” ์ฑ„๋„์—์„œ +1๋œ ์ฑ„๋„๋กœ ์ด๋™ํ•˜๊ณ , -๋ฅผ ๋ˆ„๋ฅด๋ฉด -1๋œ ์ฑ„๋„๋กœ ์ด๋™ํ•œ๋‹ค. ์ฑ„๋„ 0์—์„œ -๋ฅผ ๋ˆ„๋ฅธ ๊ฒฝ์šฐ์—๋Š” ์ฑ„๋„์ด ๋ณ€ํ•˜์ง€ ์•Š๊ณ , ์ฑ„๋„์€ ๋ฌดํ•œ๋Œ€ ๋งŒํผ ์žˆ๋‹ค.

์ˆ˜๋นˆ์ด๊ฐ€ ์ง€๊ธˆ ์ด๋™ํ•˜๋ ค๊ณ  ํ•˜๋Š” ์ฑ„๋„์€ N์ด๋‹ค. ์–ด๋–ค ๋ฒ„ํŠผ์ด ๊ณ ์žฅ๋‚ฌ๋Š”์ง€ ์ฃผ์–ด์กŒ์„ ๋•Œ, ์ฑ„๋„ N์œผ๋กœ ์ด๋™ํ•˜๊ธฐ ์œ„ํ•ด์„œ ๋ฒ„ํŠผ์„ ์ตœ์†Œ ๋ช‡ ๋ฒˆ ๋ˆŒ๋Ÿฌ์•ผํ•˜๋Š”์ง€ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค.

์ˆ˜๋นˆ์ด๊ฐ€ ์ง€๊ธˆ ๋ณด๊ณ  ์žˆ๋Š” ์ฑ„๋„์€ 100๋ฒˆ์ด๋‹ค.

 

์ž…๋ ฅ

์ฒซ์งธ ์ค„์— ์ˆ˜๋นˆ์ด๊ฐ€ ์ด๋™ํ•˜๋ ค๊ณ  ํ•˜๋Š” ์ฑ„๋„ N (0 ≤ N ≤ 500,000)์ด ์ฃผ์–ด์ง„๋‹ค. ๋‘˜์งธ ์ค„์—๋Š” ๊ณ ์žฅ๋‚œ ๋ฒ„ํŠผ์˜ ๊ฐœ์ˆ˜ M (0 ≤ M ≤ 10)์ด ์ฃผ์–ด์ง„๋‹ค. ๊ณ ์žฅ๋‚œ ๋ฒ„ํŠผ์ด ์žˆ๋Š” ๊ฒฝ์šฐ์—๋Š” ์…‹์งธ ์ค„์—๋Š” ๊ณ ์žฅ๋‚œ ๋ฒ„ํŠผ์ด ์ฃผ์–ด์ง€๋ฉฐ, ๊ฐ™์€ ๋ฒ„ํŠผ์ด ์—ฌ๋Ÿฌ ๋ฒˆ ์ฃผ์–ด์ง€๋Š” ๊ฒฝ์šฐ๋Š” ์—†๋‹ค.

 

 

์ถœ๋ ฅ

์ฒซ์งธ ์ค„์— ์ฑ„๋„ N์œผ๋กœ ์ด๋™ํ•˜๊ธฐ ์œ„ํ•ด ๋ฒ„ํŠผ์„ ์ตœ์†Œ ๋ช‡ ๋ฒˆ ๋ˆŒ๋Ÿฌ์•ผ ํ•˜๋Š”์ง€๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค.

 

 

ํ’€์ด๊ณผ์ •

์ฒ˜์Œ์—๋Š” ๋ฌธ์ œ์˜ ์ ‘๊ทผ์„ n์˜ ๊ทผ์‚ฌ๊ฐ’์„ ๊ธฐ์ค€์œผ๋กœ ์‚ผ๊ณ  ๋กœ์ง์„ ๊ตฌ์„ฑํ•˜๋Š” ๋ฐฉ์‹์œผ๋กœ ์ง„ํ–‰ํ–ˆ์—ˆ๋Š”๋ฐ ๊ทธ ๋ฐฉ์‹์œผ๋กœ ํ•˜๋‹ˆ 

์˜ˆ์ œ ์ž…๋ ฅ 7์—์„œ ๋ฌธ์ œ๊ฐ€ ๋ฐœ์ƒ๋˜์—ˆ๋‹ค.

์˜ˆ์ œ ์ž…๋ ฅ 7 ๊ฐ™์€ ๊ฒฝ์šฐ์—๋Š” 80000์— ๊ฒฝ์šฐ 77777์ด๋ผ๋Š” ๊ฐ’์„ ๋งŒ๋“ค์–ด์„œ ์ ‘๊ทผ์„ ํ•˜๋Š” ๋ฐฉ์‹์œผ๋กœ ํ•ด์•ผ 2228์ด ๋‚˜์˜ค์ง€๋งŒ

๊ทผ์‚ฌ๊ฐ’ ๊ธฐ์ค€์œผ๋กœ ์ˆซ์ž๋ฅผ ๊ตฌํ•˜๋ฉด 70000์ด๋ผ๋Š” ๊ฐ’์ด ๋‚˜์™€ ์›ํ•˜๋Š” ๊ฐ’์„ ๋„์ถœํ•ด ๋‚ผ์ˆ˜๊ฐ€ ์—†์—ˆ๋‹ค.

๊ทธ๋ž˜์„œ ํ’€์ด ๋ฐฉ์‹์„ ๋ฐ”๊ฟ”

n๋ณด๋‹ค ์ž‘์ง€๋งŒ ๊ฐ€์žฅ ํฐ ์ˆ˜์™€ n๋ณด๋‹ค ํฌ์ง€๋งŒ ๊ฐ€์žฅ ์ž‘์€ ์ˆ˜๋ฅผ ๊ตฌํ•ด ๋‘˜ ์ค‘ ๋ฒ„ํŠผ ํšŸ์ˆ˜๊ฐ€ ์ž‘์€ ๊ฐ’์„ ์ถœ๋ ฅํ•ด๋‚ด๋Š” ๋ฐฉ์‹์„ ์‚ฌ์šฉํ•˜์˜€์Šต๋‹ˆ๋‹ค.

 

code

#include <iostream>
#include <string>

int		number[10];
bool	arr[1000001];

int		main(void)
{
	int n, m, temp, max, min, answer;
	std::string s, x;

	std::cin >> n >> m;
	for (int i = 0; i < m; i++)
	{
		std::cin >> temp;
		number[temp] = 1;
	}
	for (int i = 0; i <= 1000000; i++) {
		s = std::to_string(i);
		for (int j = 0; j < s.length(); j++) {
			if (number[s[j] - '0']) {
				arr[i] = true;
				break;
			}
		}
	}
	for (int i = n; ; i++) {
		if (!arr[i]) {
			max = i;
			break;
		}
	}
	min = -1;
	for (int i = n; ; i--) {
		if (!arr[i]) {
			min = i;
			break;
		}
	}
	int minLength, maxLength;

	minLength = (std::to_string(min)).length();
	maxLength = (std::to_string(max)).length();
	answer = std::min(n - min + minLength, max - n + maxLength);
	if (min == -1) answer = max - n + maxLength;
	answer = std::min(answer, std::abs(n - 100));
	std::cout << answer << "\n";

	return (0);
}

 

ํ›„๊ธฐ

๋กœ์ง ๊ตฌ์„ฑํ•˜๊ธฐ๊ฐ€ ๊นŒ๋‹ค๋กœ์› ๋‹ค๊ตฌ๋ฆฌ๊ตฌ๋ฆฌ