[백준 16936] 나3곱2

1. 문제 이해

나3곱2 게임의 결과 수열 A를 출력하면 된다.

나3곱2 게임은 다음과 같다.

• 나3: x를 3으로 나눈다. x는 3으로 나누어 떨어져야 한다.
• 곱2: x에 2를 곱한다.

입력으로 수열 B가 주어진다. B는 수열 A의 순서를 섞은 배열이다.

 

2. 조건

B에 포함된 원소가 int 형을 넘음(10^18)

 

3. 풀이

- 수열인가 생각했음 -> 뒤에 숫자 있으면 굳이 안봐도 됨 -> 브루트포스로 고고

 

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

int main() {
    int n;
    long long num;
    vector<long long> v;

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> num;
        v.push_back(num);
    }

    for (int i = 0; i < n; i++) {
        vector<long long> vec;
        vec.push_back(v[i]);

        while (vec.size() < n) {
            bool isFlag = false; //vec에 넣은 게 있는지

            // 2 곱하기
            for (int j = 0; j < n; j++) {
                if ((vec.back() * 2) == v[j]) {
                    vec.push_back(v[j]);
                    isFlag = true;
                    break;
                }
            }
            // 3 나누기
            if (!(vec.back() % 3)) {
                for (int j = 0; j < n; j++) {
                    if ((vec.back() / 3) == v[j]) {
                        vec.push_back(v[j]);
                        isFlag = true;
                        break;
                    }
                }
            }

            if (!isFlag) {
                break;
            }
        }
        if (vec.size() == n) {
            for (auto vv: vec) {
                cout << vv << " ";
            }
            break;
        }
    }
    return 0;
}

4. 구현/디버깅

testcase를

3

100000000000000000 300000000000000000 150000000000000000로 해봤더니 안되더라

놀랍게도 input을 int형으로 받고 그걸 longlong에 담았다 ...

자료형 때문에 틀리는 경우가 요즘 잦은 거 같다ㅠ

잘보자 !!!!