[ 백준 ] 16936 / 나3곱2

金弘均·2021년 9월 16일
0

Baekjoon Online Judge

목록 보기
160/228
post-thumbnail

# Appreciation

/*
 * Problem :: 16936 / 나3곱2
 *
 * Kind :: Math
 *
 * Insight
 * - 수열 B의 임의의 한 수를 n 이라고 하자
 *   + n 은 2와 3으로만 소인수 분해하면 다음과 같이 쓸 수 있다
 *     n = x * 3^a * 2^b
 *     # 수열 A의 순서는
 *       a 가 감소하는 순서로, b 가 증가하는 순서로 나열될 수밖에 없다
 *       -> 이렇게 수열 B를 정렬해주자
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <algorithm>

using namespace std;

#define endl '\n'

// Set up : Global Variables
/* None */

// Set up : Functions Declaration
bool comp(long u, long v);


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    int N; cin >> N;
    long A[N];
    for (int i=0; i<N; i++) {
        cin >> A[i];
    }

    // Process
    sort(A, A+N, comp);

    // Control : Output
    for (int i=0; i<N; i++) {
        cout << A[i] << ' ';
    }
}

// Helper Functions
bool comp(long u, long v)
/* 비교 함수
 * u 가 v 보다 소인수 3의 개수가 많거나,
 * 소인수 3의 개수가 같으면 소인수 2의 개수가 적을 때
 * true 를 반환, 그 외 false 를 반환 */
{
    int u2 = 0, u3 = 0;
    while (u%2 == 0) {
        u2++;
        u /= 2;
    }
    while (u%3 == 0) {
        u3++;
        u /= 3;
    }

    int v2 = 0, v3 = 0;
    while (v%2 == 0) {
        v2++;
        v /= 2;
    }
    while (v%3 == 0) {
        v3++;
        v /= 3;
    }

    /* 편의상, 소인수 2의 개수에 - 를 붙여서
     * make_pair 로 비교할 수 있게끔 함 */
    return make_pair(u3, -u2) > make_pair(v3, -v2);
}
profile
이런 미친 게임을 봤나! - 옥냥이

0개의 댓글