[16936] 나3곱2

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

16936 - 나3곱2

본문

나3곱2 게임은 정수 하나를 이용한다. 가장 먼저, 정수 $x$로 시작하고, 연산을 $N-1$번 적용한다. 적용할 수 있는 연산은 두 가지 있고, 아래와 같다.

• 나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 \leq N \leq 100$)이 주어진다. 둘째 줄에는 수열 $B$가 주어진다. $B$에 포함된 원소는 $10^{18}$ 보다 작거나 같은 자연수이다.

출력

나3곱2 게임의 결과 수열 $A$를 출력한다. 항상 정답이 존재하는 경우에만 입력으로 주어지며, 가능한 정답이 여러가지인 경우에는 아무거나 출력한다.

제한

시간 제한	메모리 제한
2sec	512MB

• $2 \leq N \leq 100$
• $1 \leq B_i \leq 10^{18}$

---

풀이

코드 최종 수정일로부터 1년 반 전에 이 문제를 처음 풀었는데, 그 때 풀이 방식과 최종 수정일 기준 풀이 방식이 소름돋게 똑같다.

먼저 입력으로 주어지는 숫자들은 자연수다. 따라서 $0$은 입력으로 주어지지 않는다. 문제를 풀 때 핵심으로 사용할 수 있는 정보는, 각 숫자에는 단 2개의 연산만을 사용할 수 있다는 점이다. ‘나3, 곱2’인데, 어떤 수 $a$가 있다면 ‘나3’을 실행하면 $a$의 소인수분해 값에서 $3$을 하나 제거하는 것과 같고, ‘곱2’를 실행하면 $a$의 소인수분해 값에서 $2$를 하나 추가하는 것과 같다. 두 연산은 겹칠 수 없으므로 입력으로 주어지는 숫자들은 모두 다르다는 것을 알 수 있다.

그러면 중복되는 원소도 없고 원소들의 순서도 명확하게 나눌 수 있을 것 같다. 각 원소들을 소인수분해하여 $2$와 $3$을 각각 몇개 가지고 있는지 기록해둔다. 그리고 “$3$을 소인수로 가장 많이 가진 순서”대로 정렬을 하면 된다. 만약 그 수가 같다면 “$2$를 소인수로 가장 적게 가진 순서”로 정렬하면 된다. 수열은 항상 만들어진다고 보장하므로 이대로만 정렬하면 수열 $A$를 쉽게 얻을 수 있다.

• 참고 알고리즘 :

코드

사용 언어 : C

최종 수정일 : 2023 / 1 / 21

#include <stdio.h>

typedef long long ll;
typedef struct Node {
    ll i;
    int div2, div3;
} ND;

#define MAX_IDX 100
ND arr[MAX_IDX];
int n;

int cmp(ND* a, ND* b) {
    if (a->div3 == b->div3) {
        return a->div2 > b->div2;
    } else {
        return a->div3 < b->div3;
    }
}

ND getDivisor(ll x) {
    int d2 = 0, d3 = 0;
    ll a = x;
    while (x % 2 == 0) {
        x /= 2, ++d2;
    }
    while (x % 3 == 0) {
        x /= 3, ++d3;
    }
    return (ND){a, d2, d3};
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        ll a;
        scanf("%lld", &a);
        arr[i] = getDivisor(a);
    }

    qsort(arr, n, sizeof(ND), cmp);
    for (int i = 0; i < n; ++i) {
        printf("%lld ", arr[i].i);
    }
    return 0;
}