백준 / 16936 / 나3곱2 / C++

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

#include <bits/stdc++.h>

using namespace std;

int n;
long long int startpoint;
vector<long long int> save;

void recur(long long int val)
{
    cout << val << " ";
    for(int i = 0; i < n; i++)
    {
        if(val % 3 == 0 && save[i] == val / 3)
        {
            recur(save[i]);
            return;
        }
        else if(save[i] % 2 == 0 && save[i] == val * 2)
        {
            recur(save[i]);
            return;
        }
    }
    return;
}

void findstart(long long int val)
{
    for(int i = 0; i < n; i++)
    {
        if(save[i] % 3 == 0 && save[i] == val * 3)
        {
            findstart(save[i]);
            return;
        }
        else if(val % 2 == 0 && save[i] == val / 2)
        {
            findstart(save[i]);
            return;
        }
    }
    startpoint = val;
    return;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    //freopen("test.txt", "rt", stdin);
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        long long int tmp;
        cin >> tmp;
        save.push_back(tmp);
    }
    findstart(save[0]);
    recur(startpoint);
    return 0;
}

문제에서 요구하는 것은 특정 규칙에 따라서 순서가 정해진 수열을 랜덤하게 섞은 수열을 원래 순서대로 되돌리는 것인데, 규칙이 이렇게 정의되어 있다.

• 나3: x를 3으로 나눈다. x는 3으로 나누어 떨어져야 한다.
• 곱2: x에 2를 곱한다.

이 규칙을 통해서 특정한 자리에 오는 수를 일반화해본다면, 시작할 때의 숫자를 k라고 가정하자. 그러면 그 이후에 올 수 있는 수는 나3(k / 3) 혹은 곱2(k * 2)일 것이다. 이후에 오는 계속되는 숫자들에도 동일한 규칙이 적용될 것이고, 주목해야 할 점은 2와 3은 서로소라는 것이다.

위 내용에서 특정 구간에 올 수를 $k \times 3^a \times 2^b$로 정의할 수 있는데, 이 3의 지수승과 2의 지수승은 각각에게 영향을 미치지 않는다. 따라서 이 말은 즉슨 섞여있는 배열에서 어떤 한 숫자의 위치는 하나로 고정되어 있고, 이 문제의 해답은 유일하다라는 결론을 도출할 수 있다.

이후 문제는 위의 내용을 토대로 해결했다. 해답이 유일하다는 것을 알았고, 배열의 길이가 최대 100이므로 충분히 $O(N^2)$ 시간복잡도의 로직을 사용해도 될 것 같다고 판단, 아무 숫자나 지정한 후 그 숫자로부터 나3곱2의 역연산(곱3나2)를 적용하다 보면 배열의 시작점을 찾을 수 있다라는 아이디어로 접근했다.

findstart 함수를 통해 해답 배열의 시작점을 찾은 후, recur 함수를 통해 재귀적으로 나3곱2 조건을 만족하는 배열을 찾아가며 출력했더니 AC를 받았다.