취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 10379번 문제인 5이다.
문제는 아래 링크를 확인하자.

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

주어진 수보다 큰 수 중 자릿수 '5'가 \(K\)개 이상 들어간 수를 찾는 문제이다.

어떤 자릿수 오른쪽을 모두 '5'로 채웠을 때 '5'가 필요한 개수만큼 등장할 수 있게 하는 가장 오른쪽의 자릿수를 찾아 '5'로 채우는 것을 시도하고, 자릿수 부족이나 크기의 감소 등의 이유로 실패하면 적절하게 자릿수를 증가시켜 재시도하는 것을 반복해 문제를 해결하자.

각 자리에 대한 조작 시도 횟수 상한이 일정하다는 점을 관찰하면 이와 같은 방식으로 코드를 작성해 문제를 충분히 해결할 수 있음을 알 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <string>
using namespace std;
typedef long long ll;

string s; int K;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> s >> K;
	s = "00000000000000000000" + to_string(stoll(s) + 1);
	while (1) {
		int dgt = s.size(), KK = K;
		for (auto &l:s) {
			if (l == '5') KK--;
		}
		if (KK <= 0) {
			cout << stoll(s);
			return 0;
		}
		while (KK) {
			dgt--;
			if (s[dgt] != '5') KK--;
		}
		if (s[dgt] > '5') {
			for (int i = dgt; i < s.size(); i++) s[i] = '0';
			dgt--;
			s[dgt]++;
			while (s[dgt] > '9') {
				s[dgt] = '0';
				dgt--;
				s[dgt]++;
			}
		}
		else {
			while (dgt < s.size()) {
				s[dgt] = '5';
				dgt++;
			}
			cout << stoll(s);
			return 0;
		}
		s = "00000000000000000000" + to_string(stoll(s));
	}
}