BOJ(16936) - 나3곱2

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

---

문제 설명

나3곱2 게임은 정수 x를 가지고 다음과 같은 룰을 바탕으로 하는 게임입니다.

• 나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)

---

아이디어

case1. 나3곱2 게임은 x가 결국 (3*i) * (2*j)꼴을 띄게 됩니다. 자연스럽게 3으로 많이 나눌 수 있는 수가 수열의 앞쪽에 위치하고, 3이 같다면 2를 곱하는 연산만 있으니 크기를 오름차 순으로 정렬하는 것으로 해결할 수 있습니다.

case2. N이 100까지밖에 없으니 완전탐색으로 풀릴수도 있을 것 같습니다. /3, *2를 하면서 가능한 정답이면 리턴합니다.

---

코드

//Case2
#include <bits/stdc++.h>

#define ll long long int

using namespace std;

int N;
multiset<ll> s;
bool found = false;

void Solution(ll current, multiset<ll> currentSet, vector<ll> container)
{
    if(found) return;
    if(currentSet.find(current) == currentSet.end()) return;
    container.push_back(current);
    currentSet.erase(current);
    if(currentSet.size() == 0)
    {
        found = true;
        for(const auto& val : container)
            cout << val << ' ';
    }
    if(current % 3 == 0)
        Solution(current/3, currentSet, container);
    Solution(current*2, currentSet, container);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> N;
    vector<ll> v(N);
    for(int i = 0; i < N; ++i)
    {
        cin >> v[i];
        s.insert(v[i]);
    }

    vector<ll> tmpV;
    for(int i = 0; i < N; ++i)
    {
        Solution(v[i], s, tmpV);
    }

    return 0;
}

메모리: 2424 KB, 시간: 12 ms

---

피드백 : case1이 2를 곱하는게 큰 수이니 오름차순으로 정렬하면 간편한걸 2도 소인수로 생각해서 뭔가 어렵게 생각한 것 같은 문제점이 있었다.