[BOJ 7117 // C++] Sevens, twos and zeros

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

 

이번에 볼 문제는 백준 7117번 문제인 Sevens, twos and zeros이다.
문제는 아래 링크를 확인하자.

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

7117번: Sevens, twos and zeros

0, 2, 7의 세 수로 구성할 수 있는 10자리 이하의 수는 (자릿수가 낮은 수는 leading zero가 있다고 취급해 계산하면) 총 \(3^10=59049\)가지만이 존재한다. 또한 모든 20자리 미만의 수는 위의 10자리 수 둘을 이어붙여 구성할 수 있다. 이 성질을 이용해 문제를 해결해보자.

 

먼저 dfs나 bfs등을 이용해 가능한 모든 10자리 이하 수들을 하나하나 확인해 N으로 나눈 나머지가 k가 되는 수가 존재하는지, 존재한다면 그 최솟값이 무엇인지를 구해두자. 만약 N으로 나누어떨어지는 수가 존재(0을 제외한다. 이는 s가 n 이상이어야 한다는 조건을 만족하지 못한다.)한다면 그 수를 출력해 문제를 해결할 수 있다. 그렇지 않은 경우 가능한 나머지를 기준으로 탐색해 두 10자리 수를 이어붙여 만들 수 있는 수 중 N으로 나누어떨어지는 수의 최솟값을 구해 문제를 해결할 수 있다.

 

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

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

ll cur;
int N; ll rem[500000];

void dfs(int depth) {
	int d = cur % N;
	if (d == 0) {
		if (cur >= N) {
			if (rem[0]) rem[0] = min(rem[0], cur);
			else rem[0] = cur;
		}
	}
	else {
		if (rem[d]) rem[d] = min(rem[d], cur);
		else rem[d] = cur;
	}
	
	if (depth < 10) {
		cur = cur * 10;
		dfs(depth + 1);
		cur /= 10;
		cur = cur * 10 + 2;
		dfs(depth + 1);
		cur /= 10;
		cur = cur * 10 + 7;
		dfs(depth + 1);
		cur /= 10;
	}
}

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

	cin >> N;

	dfs(0);

	if (rem[0]) cout << rem[0];
	else {
		lll ans = 0;

		for (int i = 0; i < N; i++) {
			if (!rem[i]) continue;
			int L = (10000000000LL * i) % N;
			if (L == 0) {
				lll tmp = rem[i];
				tmp *= 10000000000LL;
				if (ans) ans = min(ans, tmp);
				else ans = tmp;
			}
			else {
				int R = N - L;
				if (!rem[R]) continue;
				lll tmp = rem[i];
				tmp *= 10000000000LL;
				tmp += rem[R];

				if (ans) ans = min(ans, tmp);
				else ans = tmp;
			}
		}

		if (ans) {
			cout << (ll)(ans / 10000000000LL);
			ll val = (ll)(ans % 10000000000LL), digit = 10;
			while (val) val /= 10, digit--;
			while (digit--) cout << 0;
			cout << (ll)(ans % 10000000000LL);
		}
		else cout << "NAV";
	}
}