Algospot - 어린이날 (CHILDRENDAY)

* Algospot - 어린이날 (CHILDRENDAY, https://algospot.com/judge/problem/read/CHILDRENDAY)

  [ 분류 - BFS/ Mathematics ]

  접근 방식이 다소 까다롭다.

  N명 중 M이 하나씩 더 받기 위해선 N%ans = M이며 이 나머지에 대해 사이클이 존재함을 알아야 한다. 또한 이를 증명하는 페르마의 소정리에 대해 알고 있어야 한다.

  * 접근 방법

    1. 찾고자 하는 ans에 대해 N%ans = M이기 위해선 기저(시작 지점)은 숫자(한자리 수)부터 시작한다. 여기에 하나씩 이어붙이며 진행하는 BFS를 구성한다.

    2. 나머지이기 때문에 후보를 [0, N]으로 줄일 순 없다. 적어도 하나 이상의 장남감을 줘야하기 때문에 [0, 2*N]가 후보가 된다. N과 같거나 큰 수는 정답의 후보가 된다. 이 부분이 적어도 하나 이상의 선물을 받을 수 있다는 여지를 주는 것이다. 따라서 N보다 크거나 같은 부분에 나머지가 M이 나오는 최초의 값이 답이 된다.

    3. visited[]를 단순 배열이 아닌 이전 값을 쫓아 갈 수 있도록 소스를 구성한다. 이 부분은 최대유량(벨만)에 유용하게 사용되므로 익혀두면 좋다.

Comment : 1,3은 맞았으나 2.에서 범위를 [0, N]으로 두고 풀어서 결국 책을 본 문제다. 좀 아쉽다 ㅠ

- 코드

#include <iostream>
#include <queue>
#include <cstring>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
using ll = long long;

int main(){
	char D[12];
	int T, M, v, i, Di, parent[20001];
	ll u, N;
	queue<ll> q;
	vector<ll> lt;
	char ans[20001];
	scanf("%d\n", &T);
	while (T--) {
		cin >> D >> N >> M;
		memset(parent, -1, sizeof parent);
		while (!q.empty()) q.pop();
		lt.clear();
		lt.resize(0);
		for (i = 0; D[i]; i++) {
			Di = D[i] - '0';
			lt.push_back(Di);
		}
		sort(lt.begin(), lt.end());
		ans[0] = 0;
		parent[0] = 0;
		q.push(0);
		while (!q.empty()) {
			u = q.front(), q.pop();
			for (ll& l : lt) {
				v = u * 10 + l;
				if (v >= N) v = N + v % N;
				else v %= N;
				if(parent[v] == -1) {
					parent[v] = u;
					q.push(v);
					ans[v] = l + '0';
				}
			}
		}
		if (parent[N + M] != -1) {
			u = N + M;
			string res = "";
			while (parent[u] != u) {
				res += ans[u];
				u = parent[u];
			}
			reverse(res.begin(), res.end());
			cout << res << '\n';
		}
		else puts("IMPOSSIBLE");
	}
	return 0;
}