[백준 27515번] 1차원 2048과 쿼리 (C++)

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

27515번: 1차원 2048과 쿼리

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

ll arr[64]; //0~63

ll func(ll n) //지수 구하기
{
    ll cnt = 0;
    while(n > 0) //2로 나눠가면서 카운트
    {
        n /=2;
        cnt++;
    }
    return cnt-1;
}

ll cal()
{
    ll copy_arr[64];   
    memcpy(&copy_arr, &arr, sizeof(arr));

    for(int i=0; i<=62; i++)
    {
        if(copy_arr[i] >=2) //2개 이상이면 다음값에 현재값/2한 값을 더해줌(합쳐져서 다음값 생성)
        {
            copy_arr[i+1] += floor(copy_arr[i]/2);
        }
    }

    for(int i=63; i>=0; i--) //가장 큰 거듭제곱 찾기
    {
        if(copy_arr[i] > 0)
        {
            return pow(2, i);
        }
    }
    return 0;
}

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

    int Q;
    cin >> Q;

    for(int i=0; i<Q; i++)
    {
        string query;
        cin >> query;

        char oper = query[0];
        string num = query.substr(1);

        if(oper == '+') arr[func(stoll(num))]++;
        else arr[func(stoll(num))]--;

        cout << cal() <<"\n";
    }

    return 0;
}

2중 반복문으로 시도하다가 시간초과를 뒤늦게 보고 다른 사람의 풀이를 참고하여 풀었다.

다른 사람 풀이를 보니 방향을 아에 잘못 잡은 것을 알 수 있었다.

 

먼저 배열을 선언하고 이 배열을 통해 2의 몇제곱인지를 표시한다.

따라서 처음 수를 입력받으면 그 수를 2로 계속 나눠서 몇제곱인지를 카운팅하여 배열에 해당 제곱수인 칸을 증가시칸다.

만약 부호가 -이면 반대로 감소시킨다.

 

그리고 배열의 다음 값으로 넘어갈수록 2제곱이 된다는 것을 이용하여 현재 값 (현재 제곱수의 갯수) 이 2가 넘는다면,

현재 값의 / 2 만큼 값을 다음 칸에 더해준다.

이는 같은 값을 2개 더해서 큰 값이 생긴 것을 표현한 것이다. 

따라서 현재 값의 / 2 만큼의 값을 다음 칸에 더 해준 것은 큰 값이 생겼으므로 생긴 횟수를 더해준 것이다.

이를 반복해주면서 계속해서 2048의 규칙을 맞출 수 있다.

 

그리고 배열의 뒷부분일수록 값이 크므로, 뒤에서 부터 반복문을 돌리며 해당 값이 있을 때 해당 인덱스 값만큼 2의 거듭제곱을 반복한 값을 반환한다.

 

이 문제를 제출하면서 out of range 오류를 매우 많이 봤는데, 처음에 배열 범위를 잘못 선언한줄 알고 오답만 엄청 늘렸다.

찾아보다보니 문자열을 숫자로 변환해주는 함수인 stoi의 문제였다.

문제의 주어진 범위에 입력값이 int를 초과하지만 (2의 62제곱) stoi는 int로 변환하는 것이기 때문이다.

따라서 stoi가 아닌, long long 범위를 이용한 stoll로 바꾸고 이에 따라 각 함수로 long long으로 바꿔주니 맞출 수 있었다.