취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 16936번 문제인 나3곱2이다.
문제는 아래 링크를 확인하자.

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

연산 과정을 통해 곱할 수 있는 수는 2 뿐이고, 3만을 나누므로 주어진 숫자들 중 소인수 3을 가장 많이 가진 수들이 수열의 앞쪽에 나오게 될 것이라는 것을 알 수 있다.

또한 소인수 3의 개수가 같다면 남은 연산은 2를 곱하는 것 뿐이므로 작은 숫자가 먼저 나올 수밖에 없다.

따라서 주어진 수들을 (1) 소인수 3의 개수 내림차순으로, 그 개수가 같다면 (2) 크기순 오름차순으로 정렬하는 것으로 문제를 해결할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

struct num {
	ll x, cnt;
	num() {
		this->x = 0, this->cnt = 0;
	}
	num(ll x, ll cnt) {
		this->x = x, this->cnt = cnt;
	}
};

bool comp(num n1, num n2) {
	if (n1.cnt != n2.cnt) return n1.cnt > n2.cnt;
	return n1.x < n2.x;
}

num arr[100];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N; cin >> N;
	for (int i = 0; i < N; i++) {
		ll x; cin >> x;
		ll xx = x, cnt = 0;
		while (xx % 3 == 0) {
			xx /= 3;
			cnt++;
		}
		arr[i] = num(x, cnt);
	}

	sort(arr, arr + N, comp);
	for (int i = 0; i < N; i++) cout << arr[i].x << ' ';
}