문제

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

풀이

수열 A가 주어지면 나누기 3을 하거나 곱하기 2만 하여 만들 수 있는 수열을 출력하는 것이다.

문제의 핵심은 모든 수 들이 중복되지 않는다는 것이다. 항상 정답이 존재하는 경우에만 입력이 주어지므로 2와 3은 서로소이기 때문에 곱하기 2를 하거나 나누기 3을 했을 때 같은 수가 나올 수 없다.

예를 들면 12의 경우 6에서 2를 곱해 만들 수 있고, 36에서 3으로 나눠 만들 수 있지만 6->36, 36->6의 경로 또한 만들어야 한다. 하지만 x2x3, /2/3 으로 x2, /3만으로 만들 수 없는 경로 이므로 중복될 수 없다.

이와 같은 이유로 맨 처음 숫자는 수열에서 x2, /3을 하여 만들 수 없는 숫자일 것이다. 시작점을 start로 설정하고 집합에 x2, 또는 /3을 한 숫자가 있으면 출력해주고, 다시 start를 설정하는 반복을 통하여 문제를 해결하였다.

소스 코드

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

set<ll> s;
ll arr[101];
int N;

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
		s.insert(arr[i]);
	}

	ll start;
	for (int i = 0; i < N; i++) {
		bool flag = true;
		for (int j = 0; j < N; j++) {
			if (i == j)
				continue;
			if (arr[j] % 3 == 0 && arr[j] / 3 == arr[i]) {				
				flag = false;
				break;
			}
			else {
				if (arr[j] * 2 == arr[i]) {
					flag = false;
					break;
				}
			}
		}
		if (flag == true) {
			start = arr[i];
			break;
		}
	}

	cout << start << " ";
	for (int i = 1; i < N; i++) {
		if (start % 3 == 0 && s.find(start / 3) != s.end()) { // 있다면
			start = start / 3;
		}
		else {
			start = start * 2;
		}
		cout << start << " ";
	}

	return 0;
}