[Java] 백준 16936 (나3곱2) Gold 5

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

16936번: 나3곱2

 

Approach

Backtracking으로 BruteForce(완전탐색)를 수행하는 문제이다.

 

만들 수 있는 모든 경우의 수를 탐색하기 위해 백트랙킹 기법을 사용하였다.

모든 숫자를 시작 숫자로 시도해 보아야 한다.

• 3으로 나누어 떨어지면, 3으로 나눈 수가 배열에서 아직 사용이 되지 않았는지 검사하고 재귀 호출한다.
• 2를 곱한 수가 배열에서 아직 사용이 되지 안았는지 검사하고 재귀 호출한다.

배열을 정렬함으로써 약간의 시간적 이득을 취할 수 있다.

(현재 숫자의 배열 인덱스보다 왼쪽에 있는 인덱스의 값은 항상 현재 숫자이하이다. 오른쪽 인덱스도 마찬가지다.)

주의할 점으로는 자료형이 Integer 타입이 아닌 Long타입으로 선언하여야 NumberFormatException이 발생하지 않는다는 점도 있다.

 

Code

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

/**
 *  No.16936: 나3곱2
 *  Hint: BruteForce + Backtracking + NumberFormatException
 */

public class BOJ16936 {
    static int n, depth;
    static long[] arr, ans;
    static boolean[] used;
    static boolean flag;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        arr = new long[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Long.parseLong(st.nextToken());
        }
        Arrays.sort(arr);

        ans = new long[n];
        used = new boolean[n];
        depth = 0;

        // 배열의 모든 수를 시작 숫자로 하여 시도
        for (int i = 0; i < n; i++) {
            solve(i, 0);
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(ans[i] + " ");
        }

        bw.write(sb.toString().trim());
        bw.close();
        br.close();
    }

    // backtracking
    static void solve(int idx, int depth) {
        if (flag) { // 정답을 찾았는지에 관한 flag
            return;
        }

        // arr[idx] 를 사용했는지 판단
        if (!used[idx]) {
            used[idx] = true;   // 사용
            ans[depth] = arr[idx];
            if (depth == n - 1) {   // arr의 모든 수를 다 사용했다면
                flag = true;
                return;
            }

            if (ans[depth] % 3 == 0) {  // 3으로 나눠지는 경우
                for (int i = idx - 1; i >= 0; i--) {    // idx보다 작은 인덱스에는 arr[idx]이하 값만 있음
                    if (arr[i] == ans[depth] / 3) {
                        solve(i, depth + 1);
                        break;
                    }
                }
            }

            for (int i = idx + 1; i < n; i++) { // idx보다 큰 인덱스에는 arr[idx]이상 값만 있음
                if (arr[i] == ans[depth] * 2) {
                    solve(i, depth + 1);
                    break;
                }
            }

            used[idx] = false;  // 사용 해제
        }
    }
}