SWEA - 10806번 수 만들기 (C++)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AXTC4piqD_IDFASe

SW Expert Academy

 

 

A수 -> B수 이동 최소거리는 유서깊을 정도로 흔한 레파토리이다. 그래서 처음 생각한 풀이는 다익스트라였다.

왜냐하면 K = 1억이고 방문체크만해준다면 O(N)으로 풀이할 수 있기 때문이다.

그러나 이 방법을 사용하려면 최악의 경우 1억개 모두 dist 배열에 + 한 갯수를 저장해야하는데 이러면 

 

int 배열을 사용하면 4억 바이트 = 4000KB = 약 400MB를 사용해야해서 불가능하다.

 

그래서 이 문제는 K부터 시작하되, 지금까지 덧셈이 가장 안된 경우 부터 검사를 해야한다. 

그래서 bfs에서 일반큐 대신 우선순위큐를 사용하면 문제를 풀 수 있다. 오히려 알고리즘은 다익스트라보다 간단해지는데 아이디어 문제라고 생각한다.

 

그리고 시도는 안해봤지만 0-1 bfs로도 풀 수 있지 않을까 생각된다.

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
	int T; 
	cin >> T;
	for (int t = 1; t <= T; t++) {
		int N, K;
		
		vector<int> arr;
		cin >> N;

		for (int i = 0; i < N; i++) {
			int tmp;
			cin >> tmp;
			arr.push_back(tmp);
		}
		cin >> K;
		priority_queue<pair<int, int>> q;

		q.push({ 0, K }); // value, cnt
		int answer = 0;
		while (!q.empty()) {
			int cnt = -q.top().first;
			int value = q.top().second;
			q.pop();

			if (value == 0) {
				answer = cnt;
				break;
			}
			
			for (int i = 0; i < N; i++) {
					q.push({ -(cnt + value % arr[i]), value / arr[i]});	
			}
		}

		cout << "#" << t << " " << answer << '\n';
	}
}