백준 16936번: 나3곱2

문제 설명

• https://www.acmicpc.net/problem/16936
• 주어진 입력값에서 인접한 두 수 a,b에 대해 항상 b = 2*a 또는 b = a/3이 성립하도록 정렬하는 문제입니다.

접근법

• 백트래킹으로 문제를 해결할 수 있습니다.
• 두 수 a,b에 대해 항상 b = 2*a 또는 b = a/3이 성립하는 조건을 고려할 때 처음에 조건을 만족하지 않으면 continue를 진행하는 방식으로 코드를 설계했습니다. 이렇게 할 경우 백트래킹(재귀) 코드 다음 방문배열을 초기화 하는 부분까지 건너뛰기 때문에 문제가 생깁니다. 그래서 if문으로 백트래킹(재귀)부분만 감싸줬습니다.

정답

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

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		long[] arr = new long[N];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			arr[i] = Long.parseLong(st.nextToken());
		}
		BackT(0,N,arr,new long[N], new boolean[N]);
	}
	
	public static boolean BackT(int depth, int N, long[] arr, long[] answer, boolean[] v) {
		if(depth == N) {
			StringBuilder sb = new StringBuilder();
			for (int i = 0; i < N; i++) {
				sb.append(answer[i]);
				sb.append(" ");
			}
			System.out.println(sb.toString());
			return true;
		}		
		for (int i = 0; i < N; i++) {
			if(v[i]) continue;
			v[i] = true;
			answer[depth] = arr[i];
			// if(depth >= 1 && !isValidate(answer[depth-1],answer[depth])) continue;
			if(depth == 0  || isValidate(answer[depth-1], answer[depth])) {				
				if(BackT(depth+1,N,arr,answer,v)) return true;
			}
			v[i] = false;
			answer[depth] = 0;
		}
		return false;
	}
	
	public static boolean isValidate(long a, long b) {
		if(a == b*3 || a*2 == b) return true;
		return false;
	}
}