[BOJ 1490 // C++] 자리수로 나누기

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

 

이번에 볼 문제는 백준 1940번 문제인 자리수로 나누기이다.
문제는 아래 링크를 확인하자.

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

 

1, 2, 3, 4, 5, 6, 7, 8, 9의 최소공배수는 2520이다. 따라서 모든 2520의 배수는 0을 제외한 모든 각 자릿수로 나누어떨어짐을 알 수 있다.

 

위 관찰을 토대로 생각하면, 아무 것도 안 붙이기, 0~9, 00~99, 000~999, 0000~9999를 붙인 수 중에서 답이 항상 존재함을 알아낼 수 있다. 즉, 많아야 11111가지 수(실제로는 이보다 적다. 0000~9999 사이에 적어도 3개의 수는 2520의 배수이기 때문이다.)에 대해 모든 자릿수로 나누어지는지 확인하는 것으로 문제를 해결할 수 있다.

 

위 내용을 구현한 코드를 작성해 문제를 해결하자.

 

새로 만들어진 수의 각 자릿수로 나누어떨어지는지를 확인하는 문제가 아님에 유의하자. 즉, 새로 만든 수가 새로 추가된 자릿수로 나누어떨어지는지는 확인하지 않아야 한다.

 

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

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

string s;
ll N;
vector<ll> dgt;
bool chk(string A) {
	N = stoll(A);
	for (auto &x : dgt) {
		if (N % x) return 0;
	}
	return 1;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> s;
	for (auto &l : s) {
		if (l == '0') continue;
		dgt.emplace_back(l - '0');
	}
	
	if (chk(s)) {
		cout << s;
		return 0;
	}

	for (int i = 0; i < 10; i++) {
		string tmp = to_string(i);
		while (tmp.length() < 1) tmp = "0" + tmp;
		if (chk(s + tmp)) {
			cout << s << tmp;
			return 0;
		}
	}
	for (int i = 0; i < 100; i++) {
		string tmp = to_string(i);
		while (tmp.length() < 2) tmp = "0" + tmp;
		if (chk(s + tmp)) {
			cout << s << tmp;
			return 0;
		}
	}
	for (int i = 0; i < 1000; i++) {
		string tmp = to_string(i);
		while (tmp.length() < 3) tmp = "0" + tmp;
		if (chk(s + tmp)) {
			cout << s << tmp;
			return 0;
		}
	}
	for (int i = 0; i < 10000; i++) {
		string tmp = to_string(i);
		while (tmp.length() < 4) tmp = "0" + tmp;
		if (chk(s + tmp)) {
			cout << s << tmp;
			return 0;
		}
	}
}