[백준/C++] 16936번 나3곱2

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

16936번: 나3곱2

어려워 보이지만 차근차근 따져보면 쉽게 풀리는 문제이다.

이 문제에서 가능한 연산은 오직 나누기3과 곱하기2 뿐이다.

그렇다면, 맨 앞에는 어떤 수가 와야할까? -> 인수3을 가장 많이 가지고 있는 숫자가 맨 앞에 와야한다!

왜 그럴까? 6 9를 예시로 보자, 6에서 9를 만들 수 있을까 라고 물어보면 답은 절대 불가능하다 이다. 15와 9를 예시로 들어도 마찬가지이다.

1. 곱하기2와 나누기3으로는 3^n의 배수로 3^m의 배수를 만들 수 없다. (n < m)

이걸로 끝은 아니다.

인수3을 똑같이 1개씩 가지고 있다고 해보자. 예를 들면 3과 6이 있을 수 있다. 둘 중 누가 먼저 와야할까?                                                   답은 한눈에 보인다. 당연히 작은 수가 앞서야지만 곱하기2 연산을 통해 만들 수 있기 때문.

2. a * 3^n의 배수와 b * 3^n의 배수가 왔을 때 a < b라면 나누기3과 곱하기2를 통해서는 b를 a로 만들 수 없다. = a가 앞에 와야한다.    (b = a * 2^x , x = 1,2,...)

728x90

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;

int n;
ull tmp;
vector<pair<ull,int>> v;

bool cmp(const pair<ull,int>& v1, const pair<ull,int>& v2){
    // 인수 3을 제일 많이 가지는 수가 맨 앞으로,
    // 만약 동일하다면, 작은 수가 앞으로 와야함.
    // why? 4와 8은 둘다 인수3을 0개 가지는데, 8에서 4를 나누기3과 곱하기 2를 통해 만들 수 없기 때문
    if(v1.second == v2.second) return v1.first < v2.first;
    return v1.second > v2.second;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n;
    for(int i=0; i<n;i++){
        ull num; int cnt=0;
        cin >> num;
        tmp = num;
        while(tmp%3==0){
            tmp /= 3;
            cnt++;
        }
        v.push_back({num,cnt}); // 숫자와 인수3의 개수 저장
    }
    // 키포인트 : 인수 3을 가장 많이 가진 숫자가 맨 앞에 와야한다!
    // 3 9를 보면 3에서 9를 곱하기2와 나누기3 연산만으론 절대 만들 수 없음
    sort(v.begin(),v.end(), cmp);

    for(auto i : v){
        cout << i.first << ' ';
    }

    return 0;
}