[ boj : 16936 ] 나3곱2

www.acmicpc.net/problem/16936

16936번: 나3곱2

문제 : 3으로 나누어 떨어지면 나누고, 2를 곱하는 동작을 한번 할 수 있습니다. 이때 n 개의 정수가 주어질때 이 n개의 정수를 적절히 나열하여서 규칙에 맞게 순서를 정해주세요

 

해설 : 먼저 문제에서 항상 답은 존재한다고 했으니 예외상황에 대해선 굳이 생각할 필요가 없겠죠.

그럼 단순하게 생각해봤을때 모든 가능한 경우의 수를 해보면 됩니다. 단, 조금 신경써서 펙토리얼을 사용할 수는 없다는 것을 n의 범위를 통해 알 수 있죠(n<=100) 100! 은 어마어마한 수가 되니까요.

 

좀더 지혜롭게 풀어볼 수 있는지 생각해 봅시다.

먼저 주어진 수들 내에서만 답을 찾을 수 있습니다. 어떤 수가 추가 되거나 제거가 되면 안된다는 뜻입니다.

그러면 시작 수를 정해놓고 3을 나누거나 2를 곱하는 동작을 n번 해봅니다. 그리고 나서 나열된 수가 주어진 조건에 맞는지 확인을 하면 됩니다.

이때 우린 bfs를 사용해서 O(n)의 시간에 할 수 있도록 해줍니다. 여기서 시간을 더 줄여주기 위해 동작을 한번 하려고 할때 주어진 수열의 수가 아닌 다른 수가 들어온다면 굳이 추가해서 연산을 해줄 필요가 없겠죠. 이를 걸러줍니다.

 

전 map을 이용해서 수열을 전부 탐색하여 만약 n번의 동작이 끝나고 나서도 큐가 비어있지 않았다면 조건들을 만족했다는 뜻이니 제일 처음의 수열을 출력하게끔 해주었습니다.

 

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

struct info {
	ll x;
	vector<ll> v;
};
int n;
ll arr[100];
map<ll, int> m;

void bfs(ll x);

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

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
		m[arr[i]] += 1;
	}
	for (int i = 0; i < n; i++) 
		bfs(arr[i]);
	return 0;
}
void bfs(ll x)
{
	int time = 0;
	queue<info> q;
	q.push({ x,{x} });
	map<ll, int> mp = m;
	mp[x] -= 1;

	while (!q.empty())
	{
		for (int i = q.size(); i > 0; i--)
		{
			info cur = q.front();
			q.pop();

			if (mp.find(cur.x*2)!= mp.end() && mp[cur.x * 2] > 0) {
				mp[cur.x * 2] -= 1;
				cur.v.push_back(cur.x * 2);
				q.push({ cur.x*2,cur.v });
			}
			if (cur.x % 3 == 0 && mp.find(cur.x / 3) != mp.end() && mp[cur.x / 3] > 0) {
				mp[cur.x / 3] -= 1;
				cur.v.push_back(cur.x / 3);
				q.push({ cur.x / 3,cur.v });
			}
		}
		time++;
		if (time >= n-1)break;
	}
	if (q.empty())return;
	info cur = q.front();
	for (ll u : cur.v)
		cout << u << " ";
}