백준 [BOJ] 16936 나3곱2

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

16936번: 나3곱2

문제 해설

1. 나3 : x를 3으로 나눈다. x는 3으로 나누어 떨어져야 한다.

2. 곱2 : x를 2로 곱한다.

어떤 수 x에 1, 2 두 가지 연산을 N번 시행했을 때, 수열 A가 나온다.

이 수열 A의 순서를 뒤섞은 수열 B로부터 A를 찾아내는 문제다.

 

살펴볼 것

1. 주어진 수열에 있는 원소는 중복이 있을까?

중복은 없다.

연산은 3으로 나누거나 2로 곱하는 것뿐이다.

게임의 시작을 정수 x = q * 2^a * 3^b (q는 2, 3과 각각 서로소)로 둔다면,

다음 수는 y = q * 2^(a+1) * 3 ^(b) 이거나 y = q * 2^(a) * 3 ^(b-1)가 되고(a가 증가하거나 b가 감소한다),

이후 모든 수들은 z = q * 2^(a`) * 3^(b`) (단, (a <= a` and b >= b`) and !(a == a' and b == b`)가 될 것이다.

 

즉, 수열에 있는 임의의 수 x = q * 2^a * 3^b (q는 2, 3과 각각 서로소)를 고른다면,

x가 아닌 임의의 수 y =  q * 2^(a`) * 3^(b`) (단, a != a` 이거나 b != b`)로 표현될 수 있다.

 

 

2. 가능한 정답은 여러 개일까?

유일하다.

항상 정답이 존재하는 경우에만 입력으로 주어지므로 수열 내의 특정한 수 x를 고를 경우,

수열은 { (x/2 존재) xor (3x 존재) } or { (2x 존재) xor(x/3 존재) }를 만족해야 한다. (만족하지 않는 경우 수열엔 x뿐)

위의 중괄호 속에 있는 식을 만족하는 수가 존재한다면 수의 위치는 유일하다.(바로 앞 또는 바로 뒤)

왜냐하면, 2와 3은 서로소이고, 연산은 3으로 나누거나 2로 곱하는 것뿐이기 때문이다.

 

ex)

나4곱2문제였다면 원소들 사이 순환이 생기기 때문에 정답은 유일하지 않다.

나3곱3문제인경우도 같은 이유로 정답이 유일하지 않다.

 

해답

정답이 유일하므로, 주어진 원소 중 아무 수 x를 고른다면,

수열이 { (x/2 존재) xor (3x 존재) } or { (2x 존재) xor(x/3 존재) }를 만족하거나, 더 이상의 원소가 없다.

앞의 중괄호 { (x/2 존재) xor (3x 존재) }를 만족하는 수가 존재한다면, 정렬되었을 때 해당 수는 x 앞에,

뒤의 중괄호 { (2x 존재) xor(x/3 존재) }를 만족하는 수가 존재한다면, 정렬되었을 때 해당 수는 x 뒤에 위치하게 될 것이다.

이제 우리는 해당 수가 있는지 없는지만 판단하면 되므로, 유일한 값들을 저장하는 set으로부터 만족하는 수를 찾으면 된다. 그리고, 찾은 수는 x앞 혹은 뒤에 존재해야 하므로 deque를 이용해 양방향 모두 입력받도록 한다.

#include <iostream>
#define fio cin.tie(0)->sync_with_stdio(0)
using namespace std;

#include <set>
#include <deque>
using ll = long long;

int main() {
	fio;
    set<ll> set_;
    int N; cin>>N;
    ll start; cin >> start;
    set_.insert(start);
    for(int i=0; i <N-1;i++){
        ll tmp; cin >> tmp;
        set_.insert(tmp);
    }
    //
    deque<ll> dq;
    dq.push_back(start);
    //
    ll now;
    now = start;
    while(1){//to the left
        ll prev = now;
        if(now % 2 == 0 && set_.find(now/2) != set_.end()){
            prev = now/2;
        }
        if(set_.find(now*3) != set_.end()){
            prev = now*3;
        }
        if(prev == now){//둘 다 없는 경우
            if(set_.find(now) != set_.end())
                set_.erase(now);
            break;
        }else{
            dq.push_front(prev);
                if(set_.find(now) != set_.end())
            set_.erase(now);
            now = prev;
        }
    }
    //
    now = start;
    while(1){//to the right
        ll next = now;
        if(now % 3 == 0 && set_.find(now/3) != set_.end()){
            next = now/3;
        }
        if(set_.find(now*2) != set_.end()){
            next = now*2;
        }
        if(next == now){//둘 다 없는 경우
            if(set_.find(now) != set_.end())
                set_.erase(now);
            break;
        }else{
            dq.push_back(next);
            if(set_.find(now) != set_.end())
                set_.erase(now);
            now = next;
        }
    }
    //
    while(!dq.empty()){
        cout << dq.front()<<' ';
        dq.pop_front();
    }
	return 0;
}