CHILDRENDAY(어린이날)

(출처) https://algospot.com/judge/problem/read/CHILDRENDAY

일단은 문제의 조건을 모아보자

N명의 어린이에게 사탕을 나누어 줘야 한다. 나눠줘야할 사탕의 개수는 특정 조건을 만족해야하며, 정답은 조건을 만족하는 값 중 가장 최소가 되는 값으로 결정한다.

문제에서 주어지는 특정 조건은,

1. N명의 어린이 중 M명의 어린이는 사탕을 추가로 1개씩 더 받는다.

2. 사탕의 총합 개수의 D 목록에 있는 특정 수만으로 이뤄져야한다.

3. 어린이들은 사탕을 적어도 1개씩은 받아야한다.

구하고자 하는 사탕의 총합을 RET이라 하고 사탕을 X라고 표현한다고 했을때 1번 조건을 X에 대한 수식으로 표현하면,

RET = (N - M) X + M ( X - 1 ) = NX - M으로 표현할 수 있다. 또한 X >= 1 이라는 3번 조건이 붙어있다.

따라서 1차식 NX - M (X >=1)을 만족하면서, 주어진 D 목록에 있는 수만을 이용하여 만들 수 있는 최소값을 구해내는 것이 문제의 목표라고 할 수 있다.

그래서 수식을 만족하는 답을 어떻게 찾지?

문제를 직관적인 수식으로 나타내고 해결 방법을 여러 고민을 해봤지만, D 목록에 있는 수만을 이용해서 수식을 만족하는 답을 어떻게 찾는가에 대한 아이디어는 결국 생각해내지 못했다.

그래서 책을 확인했는데 책에서는 각 정점을 RET을 N으로 나눈 나머지로 표현하고 간선을 BFS로 탐색해가며 해결하는 것을 볼 수 있었다.

나는 X를 1부터 계속 대입해보면서 1번과 3번 조건에 알맞는 수를 먼저 만들고, 이후 D 목록에 해당하는 수로만 이루어져있는 답을 찾아내는 식으로 문제를 해결할려고 했다.

하지만 책에서는 먼저 D를 이용하여 만들 수 있는 수를 만들어 가면서, 이 후 만든 수에 N을 나눠주어 1번과 3번 조건을 만족하는 수를 찾는 식으로 진행하는 것을 볼 수 있었다.

나와 같은 방법으로는 정답을 찾는 과정을 언제 종료해야하는 지(불가능한 경우)도 명확하게 단정지을 수 없었던 반면, 책의 방법대로 먼저 D의 목록으로 만들 수 있는 수를 만들어나가면서, 만든 수를 N으로 나눈 나머지를 정점으로 표현하고, 상황의 진행을 간선으로 이어주는 방식을 이용하면 D 목록으로만 구성된 수를 나타내는 형태의 그래프를 만들 수 있었고, 그로인해 종료지점도 명확하게 볼 수 있게 되었다.

즉 해당 그래프에서 수식을 만족하는 경로만을 찾아내면 되는 문제로 목표가 변환 된 것이다.

그래프를 만들고 이어서 1번과 3번 조건인 RET = NX + M (X >= 1)이라는 수식을 만족하기 위해선, RET을 N으로 나눈 나머지가 M이 되어야하므로 결국 탐색이 종료되어야하는 정점은 M이 된다.

따라서 결국 해당 그래프에서 시작점으로부터 M까지의 거리를 구하면 되는데, X가 1이상이여야 한다는 조건을 만족시키기 위해서 만든 수가 N미만일 때의 나머지를 표현하는 정점과, N이상일 때의 나머지를 표현하는 정점으로 모든 정점을 2개씩 표현한다.

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#include <string>

using namespace std;
vector<vector<pair<int, string>>> graph;
vector<int> distance_bfs;
vector<int> parent;

void making_graph(vector<int>& D, int N) {
	for (int node = 0; node < graph.size(); node++) {
		for (int edge_i = 0; edge_i < D.size(); edge_i++) {
			int next_node = (node * 10) + D[edge_i];
			if (next_node >= N ) {
				next_node %= N;
				pair<int, string> temp (N + next_node, to_string(D[edge_i]));
				graph[node].push_back(temp);
			}
			else {
				pair<int, string> temp(next_node, to_string(D[edge_i]));
				graph[node].push_back(temp);
			}
		}
	}
}

void childrenday(int here) {
	queue<int> q;
	distance_bfs[here] = 0;
	parent[here] = here;
	q.push(here);
	while (!q.empty()) {
		here = q.front();
		q.pop();
		for (int i = 0; i < graph[here].size(); i++) {
			if (distance_bfs[graph[here][i].first] == -1) {
				q.push(graph[here][i].first);
				distance_bfs[graph[here][i].first] = distance_bfs[here] + 1;
				parent[graph[here][i].first] = here;
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int tc;
	cin >> tc;
	while (tc--) {
		string d;
		cin >> d;
		int N, M;
		cin >> N >> M;
		vector<int> D;
		for (int i = 0; i < d.size(); i++) {
			int temp = d[i] - '0';
			D.push_back(temp);
		}
		graph = vector<vector<pair<int, string>>>(2 * N);
		sort(D.begin(), D.end());
		making_graph(D, N);

		distance_bfs = vector<int> (2 * N , -1);
		parent = vector<int>(2 * N, -1);
		childrenday(0);

		int target = N + M;
		if (parent[target] == -1) {
			cout << "IMPOSSIBLE" << "\n";
			continue;
		}
		string ret;
		while (target != 0) {
			int target_parent = parent[target];
			for (int i = 0; i < graph[target_parent].size(); i++) {
				if (graph[target_parent][i].first == target) {
					ret = ret + graph[target_parent][i].second;
					break;
				}
			}
			target = target_parent;
		}

		reverse(ret.begin(), ret.end());
		
		cout << ret << "\n";
	
	}
	return 0;
}

기억하고 싶은 점

해당 문제는 모든 정점을 정확하게 1번씩만 방문하여 각 정점별 시작점으로부터 떨어진 거리를 기록한 뒤 이후의 사이클을 통한 방문이라던가 추가적인 진행과정은 무시한다.

문제에서는 어차피 만들어낼 수 있는 경로의 최솟값을 요구하고 있으므로 이미 방문했던 정점들을 사이클을 반복하며 재방문하며 답을 얻어낼 필요가 없으니까 각 정점들을 단 1번씩만 방문하는 것 만으로 답을 구할 수 있는 것이 가능했던 것.

그런데 만약 문제가 2 번째 최솟값, 3 번째 최솟값, ... , K 번째 최솟값을 얻어내라는 조건이 붙어있었다면 어땠을까.

현재 코드의 구현을 약간 고친다면 답을 얻어낼 수 있을까?

이와 같은 점을 고민 해보고 탐색과 구현에 대해서 좀 더 깊게 생각해 보는 시간을 가져봐도 될 것 같다.

또한 나머지를 이용해 정점을 표현하고 간선을 나아가면서 (경로를 만들면서) 답을 하나씩 만들어 나가는 이 문제의 해결 아이디어를 보며 문제를 그래프로 변형하여 푸는 센스? 트릭 같은걸 조금은 느꼈다.

지금처럼 아직 많이 문제를 풀어보지 않은 상태에서는 문제를 풀 때 오랫동안 계속 고민하기보다는 차라리 빨리 해결 아이디어를 보면서 이런 센스같은걸 익히고 기본기를 먼저 쌓는게 나아보인다.