[Algorithm] 16936 나3곱2 C++ 문제 해결 과정

www.acmicpc.net

시간 초과를 조심하자 !

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std; 

int main() {
    int n; cin >> n;
    vector<long long> B(n);
    for (int i = 0; i < n; i++)
        cin >> B[i]; 
    sort(B.begin(), B.end()); 

    do {
        long long value= B[0];
        bool flag = true; 
        for (int i = 1; i < n; i++) {
            // 나3곱2의 경우가 아니면
            if (!(B[i] == value * 2 || (B[i] == value / 3 && value % 3 == 0))) {
                flag = false; 
                break; 
            }
            value = B[i];
        }
        if (flag)
            break;
    } while (next_permutation(B.begin(), B.end())); 

    for (int i = 0; i < n; i++)
        cout << B[i] << " "; 
    cout << endl;
    return 0; 
}

B 배열의 모든 경우를 따져보아야 한다 생각하여 next_permutation 함수를 사용하였다. 그러나 이는 시간 초과 .. (N +1)! 그러니까 최대 101!의 시간이 걸리고 이는 엄청난 ,, 시간이 걸리게 된다. 🥲🥲

따라서 이는 곱2, 나3 두 가지 연산만 할 수 있다는 점을 이용해 문제를 풀어야 한다.

해결 코드

#include <iostream>
#include <vector>
#include <cstring>
using namespace std; 

int a[101]; // a[i] : i번 다음에 올 수 있는 값은 B의 a[i]번 위치에 있다.

int main() {
    int n; cin >> n;
    vector<long long> B(n);
    for (int i = 0; i < n; i++)
        cin >> B[i]; 

    memset(a, -1, sizeof(a)); 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j) continue;
            if (B[i] * 2 == B[j]) a[i] = j;
            else if (B[i] / 3 == B[j] && B[i] % 3 == 0) a[i] = j; 
        }
    }

    // A배열에서 제일 처음 오는 값의 B 위치를 찾는다.
    int firstIndex = n * (n - 1) / 2;
    for (int i = 0; i < n; i++) {
        if (a[i] != -1)
            firstIndex -= a[i]; 
    }

    vector<long long> ret;
    ret.push_back(B[firstIndex]);

    long long nextIndex = a[firstIndex]; 
    while (a[nextIndex] != -1) {
        ret.push_back(B[nextIndex]); 
        nextIndex = a[nextIndex]; 
    }
    ret.push_back(B[nextIndex]); 
    for (int i = 0; i < ret.size(); i++)
        cout << ret[i] << " "; 
    cout << endl;
    return 0; 
}

조금 복잡해 보이는데, 이중 for문에서 배열 B의 특정 i번 숫자에서 j번 숫자로 나3곱2 연산으로 이동할 수 있다면 a[i] = j 를 입력해주었다.

그리고 배열 a 중에서 값이 -1이 되어있는, 즉 A 배열에서 앞에 다른 숫자가 없는 경우 firstIndex라고 지정해주고 a 배열을 매개체로 해서 연쇄적으로 nextIndex의 값을 구해준다. 이렇게 해서 ret에 마지막 원소까지 넣고 출력하면 끝 !

또 이런 방식으로도 풀 수 있어요 🐹

나누기 3 연산은 피연산자를 소인수분해 했을 때 3이 하나 줄어들게 된다. 또한, 곱하기 2 연산은 소인수분해 했을 때 2가 하나 늘어난다.

따라서 4, 8, 6, 3, 12, 9 라는 배열을 각각 소인수분해했을 때 가장 3의 개수가 많은 9가 A 배열에 처음으로 올 수밖에 없다. 왜냐하면 3은 줄어들 수만 있지 늘어날 수 없으니까 !

마찬가지로 가장 2의 개수가 많은 8이 A 배열의 마지막에 올 수 밖에 없다. 왜냐하면 2는 늘어날 수만 있지 줄어들 수는 없으니까 ! 따라서 아래 조건으로 바꾸어 문제를 풀 수 있다.

• count[i] : 각각의 수가 3으로 몇 번 나누어질 수 있는지 기록하여, i번째 수가 3으로 나누어지는 횟수를 저장한다.
• A 수열에서는 count[A[i]] >= count[A[i + 1]을 만족한다.
• A 수열에서는 A[i] * 2 = A[i + 1] 을 만족한다.

이렇게 count 배열을 구한 다음에 1번 조건을 이용해 정렬하고, 2번 조건을 이용해 한 번 더 정렬하면 된다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 3의 개수 기준으로 내림차순 정렬
bool cmp(pair<int, long long >& a, pair<int, long long >& b) {
    if (a.first == b.first)
        return a.second < b.second;
    else
        return a.first > b.second; 
}

int main() {
    int n; cin >> n; 
    // (3의 개수, 실제 수)
    vector<pair<int, long long>> a(n); 

    for (int i = 0; i < n; i++) {
        long long num; 
        cin >> num; 

        a[i].second = num;
        while (num % 3 == 0) { // 3의 개수 계산
            num /= 3; 
            a[i].first++; 
        }
    }
    sort(a.begin(), a.end(), cmp); 

    for (int i = 0; i < n; i++)
        cout << a[i].second << " "; 
    cout << endl;
    return 0; 
}