[BOJ 16936] 나3곱2

문제 링크 : https://www.acmicpc.net/problem/16936

문제

나3곱2 게임은 정수 하나를 이용한다. 가장 먼저, 정수 x로 시작하고, 연산을 N-1번 적용한다. 적용할 수 있는 연산은 두 가지 있고, 아래와 같다.

• 나3: x를 3으로 나눈다. x는 3으로 나누어 떨어져야 한다.
• 곱2: x에 2를 곱한다.

나3곱2 게임을 진행하면서, 만든 수를 모두 기록하면 수열 A를 만들 수 있다. 예를 들어, x = 9, N = 6이고, 적용한 연산이 곱2, 곱2, 나3, 곱2, 나3인 경우에 A = [9, 18, 36, 12, 24, 8] 이다.

수열 A의 순서를 섞은 수열 B가 주어졌을 때, 수열 A를 구해보자.

입력

첫째 줄에 수열의 크기 N(2 ≤ N ≤ 100)이 주어진다. 둘째 줄에는 수열 B가 주어진다. B에 포함된 원소는 10¹⁸ 보다 작거나 같은 자연수이다.

출력

나3곱2 게임의 결과 수열 A를 출력한다. 항상 정답이 존재하는 경우에만 입력으로 주어지며, 가능한 정답이 여러가지인 경우에는 아무거나 출력한다.

제한

시간 제한	메모리 제한
2sec	512MB

---

풀이

정수 $x$에 “3으로 나누기”와 “2 곱하기” 연산을 적용하여 만든 수열을 복원하는 문제다. 수열의 각 원소는 $3^a \cdot 2^b \cdot k$ (단, $k$는 2와 3으로 나누어지지 않는 정수)의 형태로 표현할 수 있다. 문제에서 제시된 두 가지 연산이 지수에 미치는 영향은 다음과 같다:

• 나3: $x$를 3으로 나눈다. 이는 3의 지수 $a$를 1 감소시킨다.
• 곱2: $x$에 2를 곱한다. 이는 2의 지수 $b$를 1 증가시킨다.

수열이 진행될수록 3의 지수 $a$는 결코 증가할 수 없으며(오직 감소만 가능), 2의 지수 $b$는 결코 감소할 수 없다(오직 증가만 가능). 따라서 주어진 숫자들을 원래의 순서대로 정렬하기 위해서는 각 숫자가 포함하고 있는 소인수 2와 3의 개수를 파악해야 한다.

정렬 기준은 다음과 같이 설정한다:

1. 소인수 3의 개수: 내림차순으로 정렬한다. 연산을 거칠수록 3의 지수는 줄어들기 때문이다.
2. 소인수 2의 개수: 3의 개수가 같다면, 소인수 2의 개수를 기준으로 오름차순 정렬한다. 연산을 거칠수록 2의 지수는 늘어나기 때문이다.

\[Sorted\_Criteria = \begin{cases} count(3) \downarrow \\ count(2) \uparrow & (\text{if } count(3) \text{ is same}) \end{cases}\]

수열의 크기 $N$이 최대 100으로 매우 작기 때문에, 각 숫자의 소인수 개수를 구한 뒤 정렬 알고리즘을 적용하면 $O(N \log N)$의 시간 복잡도로 충분히 해결 가능하다.

소스코드

Github Link : Source Code

참고 알고리즘 :