BOJ 27514번 : 1차원 2048

문제

---

문제 풀이 - 시간 초과

첫번째 숫자부터 반복문으로 돌아가고 같은 숫자를 찾아 변화가 생기면 재귀를 이용해 다시 처음부터 같은 숫자를 찾아 바꾸는 과정을 반복해 수열을 구한다.

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

vector<long long> v;
int n, i, k;
long long a, ans = 0;

void number(int num) {
    for (k = 0; k < n; k++) {
        if (k != num && v[k] == v[num]) {
            v[num] *= 2;
            v[k] = 0;
            number(num);
        }
    }
}

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

    cin >> n;
    for (int i = 0; i < n; i++) { // 입력
        cin >> a;
        if (a != 0) { v.push_back(a); } // 0이 아닌 경우에만 삽입
    }
    n = (int)v.size();

    for (i = 0; i < n; i++) {
        if (v[i] != 0) {
            number(i);
        }
    }

    for (long long a : v) { ans = max(a, ans); }
    cout << ans;

    return 0;
}

문제 풀이2 - 맞았습니다!

1. 입력받는 수를 모두 log2 처리 해서 지수들만 구해 배열에 저장한다.
2. 앞에서부터 2로 나눠 짝이 되는 수 만큼 다음 지수의 수에 더해준다.
3. 뒤에서부터 검사해 가장 큰 수를 찾아내 제곱해 원래의 수를 구해 답을 구한다.

맞왜틀? 코드

#include <iostream>
#include <algorithm>
#include <cmath> // log2(), pow()
using namespace std;

int arr[63];

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

    int n;
    long long l; // ~2^62는 long long
    cin >> n;

    for (int i = 0; i < n; i++) { // 입력
        cin >> l;
        if (l != 0) {
            l = log2(l);
            arr[l]++;
        }
    }

    for (int i = 0; i < 62; i++) {
        arr[i + 1] += arr[i] / 2;
    }

    for (int i = 62; i >= 0; i--) {
        if (arr[i] != 0) {
            cout << pow(2, i);
            return 0;
        }
    }

    return 0;
}

너무 맞는데... 예제도 다 잘 나오고 따로 만들어본 예제도 다 잘 나오는데... 또 구글링 해본 결과 파이썬으로 푼 정답이랑 로직이 똑같은데 대체 왜 틀린거지? 채점 시작하자마자 틀렸다고 뜬다.

맞왜틀? => POW()는 실수형을 반환한다!

어차피 출력되는 수들은 모두 정수이니 pow의 리턴값의 자료형 자체는 문제가 없지만, 그게 실수형이고, 엄청 큰 수를 커버해야하는 경우에는 문제가 생긴다.

실수형은 엄청 큰 수를 출력할 때 뒤를 잘라버린다.

48793698643297...... 이런 수를 출력하면 4.87936e+13 이렇게 뒤에가 잘린 채로 출력된다.

최종 정답 코드

출력할 때 (long long)으로 강제 형변환을 시켜줬다.

#include <iostream>
#include <algorithm>
#include <cmath> // log2(), pow()
using namespace std;

int arr[63];

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

    int n;
    long long l; // ~2^62는 long long
    cin >> n;

    for (int i = 0; i < n; i++) { // 입력
        cin >> l;
        if (l != 0) {
            l = log2(l);
            arr[l]++;
        }
    }

    for (int i = 0; i < 62; i++) {
        arr[i + 1] += arr[i] / 2;
    }

    for (int i = 62; i >= 0; i--) {
        if (arr[i] != 0) {
            cout << (long long)pow(2, i);
            return 0;
        }
    }

    return 0;
}

복습: 엄청 큰 수를 출력할 때 실수형은 대충 적당히 뒤를 잘라버린다. 주의!