[백준] 16936번 나3곱2 - Java

문제 링크

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에 포함된 원소는 1018 보다 작거나 같은 자연수이다.

출력

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

알고리즘: 수학, 정렬, 구성적

풀이

첫 번째 값을 정하고, *2, /3연산을 한다. 단 연산 결괏값은 A 수열에 존재하지 않고, B 수열에 존재하는 값이어야 함. A 수열의 길이가 N이라면 해당 수열을 출력하면 끝이다.
(첫 번째 값은 B 수열에서 차례대로 적용해본다.)

여기서, 2가지의 경우의 수로 O(n2^n)라고 생각할 수 있지만, 수열에 n이 존재할 때 n2와 n/3은 공존할 수 없다. 왜냐하면 n2로 n/3을 만들려면 /2, /3 연산이 필요하고, n/3로 n2을 만들려면 3, 2 연산이 필요하다. 즉 /2, *3 연산이 존재하지 않기 때문이다.
그래서 경우의 수는 1가지이며 시간복잡도 O(n^2)으로 충분히 TLE없이 통과할 수 있다.

소스 코드

import java.io.*;
import java.util.*;

public class Main {
    static int N;
    static ArrayList < Long > b_sn = new ArrayList < > ();
    static Stack < Long > a_sn = new Stack < > ();
    static boolean end = false;
    static StringBuilder ans = new StringBuilder();
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            b_sn.add(Long.parseLong(st.nextToken()));
        }
        for (int i = 0; i < N; i++) {
            a_sn.push(b_sn.get(i));
            DFS();
            a_sn.pop();
            if (end) break;
        }
        System.out.println(ans.toString().trim());
    }

    static void DFS() {
        if (a_sn.size() == N) {
            end = true;
            for (int i = 0; i < N; i++) {
                ans.append(String.valueOf(a_sn.get(i)) + " ");
            }
            return;
        }
        long n = a_sn.peek();
        long gob2 = n * 2;
        if (b_sn.contains(gob2) && !a_sn.contains(gob2)) {
            a_sn.push(gob2);
            DFS();
            a_sn.pop();
        } else if (n % 3 == 0) {
            long na3 = n / 3;
            if (b_sn.contains(na3) && !a_sn.contains(na3)) {
                a_sn.push(na3);
                DFS();
                a_sn.pop();
            }
        }
    }
}