16936. 나3곱2

16936번: 나3곱2

---

정수 $x$에 다음 두 연산 중 하나를 $N-1$번 적용하여 길이가 $N$인 수열 $A$를 만든다.

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

$A$의 수를 무작위로 섞은 수열 $B$가 주어졌을 때, $A$를 구하는 문제이다.

---

$A$에 속하는 정수 $y$에 대해, $y$ 앞에는 $3y$ 또는 $y/2$가 올 수 있고, $y$ 뒤에는 $y/3$ 또는 $2y$가 올 수 있다. 우리는 이 수열의 올바른 순서를 찾아야 한다. 위상 정렬처럼 생각해도 좋다.

 

연산을 잘 보면, 곱하는 수와 나누는 수가 $2$와 $3$으로 서로 다르다. 그렇다면 연산을 계속 적용했을 때 나왔던 수가 또 나오는 경우는 불가능하다. 따라서 $A$가 존재한다고 하더라도 서로 다른 $A$가 여러 개 존재할 수는 없다.

 

이로써 스페셜 저지 태그와 출력 문단의 `가능한 정답이 여러가지인 경우에는 아무거나 출력한다`는 낚시임을 알 수 있다. 이런.. ㅋㅋ

 

출력 문단에서 항상 정답이 존재하는 경우만 입력으로 주어진다고 했으니, 이제 수열을 만들기만 하면 된다.

---

 

수열 $A$가 유일하므로 $A$의 시작 원소 $x$도 유일하다. $s \in B$에 대해 $3s \notin B$이고 $s/2 \notin B$인 $s$를 찾아서, $s$를 시작 원소로 하여 $A$를 만들면 된다.

 

$N$이 최대 $100$이지만, 정답이 유일하므로 재귀 탐색으로 정답을 찾아도 시간 초과가 발생하지 않는다.

---