[알고리즘] 16936번

오늘 풀어볼 문제는 백준 16936번 문제 "나3곱2" 이다.

이 문제는 골드5 문제이고 브루트 포스 문제이다.

문제

나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를 출력한다. 항상 정답이 존재하는 경우에만 입력으로 주어지며, 가능한 정답이 여러가지인 경우에는 아무거나 출력한다.

📌첫 번째 시도📌

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static boolean[] visit;
    static boolean complete = false;
    static ArrayList<Long> arrayList = new ArrayList<>();;
    static long[] answer;
    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());

        answer = new long[N];
        visit = new boolean[N]; // 방문한 곳 확인

        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int i = 0; i < N; i++) {
            arrayList.add(Long.parseLong(st.nextToken()));
        }

        Collections.sort(arrayList); // 오름차순

        for (int i = 0; i < N; i++) {
            if (complete) {
                break;
            }
            cal(0, i);
        }

        //결과로 얻은 순서 BufferedWriter 저장
        for (int i = 0; i < N; i++)
        {
            bw.write(answer[i] + " ");
        }
        bw.flush();
        bw.close();
        br.close();
    }
    private static void cal(int count, int index) {
        if(answer[N-1]!=0) {		//올바른 순서 찾았을 때
            complete = true;		//완성!
            return;
        }

        if(!visit[index]) {
            visit[index] = true;
            answer[count] = arrayList.get(index);
            if(arrayList.get(index) % 3 == 0) {
                for (int i = index - 1; i >= 0; i--) {
                    if(arrayList.get(index) / 3 == arrayList.get(i)){
                        cal(count+1, i);
                        break;
                    }
                }
            }
            long temp = arrayList.get(index) * 2;
            for(int i = index + 1; i < N; i++) {
                if(temp == arrayList.get(i)){
                    cal(count+1, i);
                    break;
                }
            }
        }
    }
}

솔족히.. 구글의 도움을 받아서 이해하고 코드를 작성했다.
재귀 방식으로 계속 함수를 타고타고 들어가서 결론을 지었다.

그런데 실패했다.. 왜일까??

멍청하게... 조건에 옳지 않은 방향으로 갔을 때 다시 시작해야 함으로 visit 배열을 다시 false로 해야 했는데... 그걸 추가를 안 했다..

다시 그 부분을 추가해서 돌렸다.

📌두 번째 시도📌

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static boolean[] visit;
    static boolean complete = false;
    static ArrayList<Long> arrayList = new ArrayList<>();;
    static long[] answer;
    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());

        answer = new long[N];
        visit = new boolean[N]; // 방문한 곳 확인

        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int i = 0; i < N; i++) {
            arrayList.add(Long.parseLong(st.nextToken()));
        }

        Collections.sort(arrayList); // 오름차순

        for (int i = 0; i < N; i++) {
            if (complete) {
                break;
            }
            cal(0, i);
        }

        //결과로 얻은 순서 BufferedWriter 저장
        for (int i = 0; i < N; i++)
        {
            bw.write(answer[i] + " ");
        }
        bw.flush();
        bw.close();
        br.close();
    }
    private static void cal(int count, int index) {
        if(answer[N-1]!=0) {		//올바른 순서 찾았을 때
            complete = true;		//완성!
            return;
        }

        if(!visit[index]) {
            visit[index] = true;
            answer[count] = arrayList.get(index);
            if(arrayList.get(index) % 3 == 0) {
                for (int i = index - 1; i >= 0; i--) {
                    if(arrayList.get(index) / 3 == arrayList.get(i)){
                        cal(count+1, i);
                        break;
                    }
                }
            }
            long temp = arrayList.get(index) * 2;
            for(int i = index + 1; i < N; i++) {
                if(temp == arrayList.get(i)){
                    cal(count+1, i);
                    break;
                }
            }
        }
        visit[index] = false;
    }
}

물론.. 성공이다 ㅎㅎ 그런데.. 아직 골드 문제는 나에게 너무 어려운 것 같다.. 흐어어어엉

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