[백준] 28257. 알록달록 초콜릿 만들기 - C++

[Gold III]

 

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

12899번: 데이터 구조

 

 

백준 제 2회 초콜릿컵 C번 문제

대회 당일 런타임 에러로 애를 먹었던 문제다.

이분탐색할 때 vector를 사용했었는데, 큰 숫자 범위 때문에 메모리 제한을 벗어난 듯 했음.

 

풀이

조금의 규칙성(?)과, 이분 탐색을 이용해야 하는 문제.

 

우선, 첫 번째 규칙은, 각 줄에 존재하는 민트초코의 개수.

1개 0개 1개 / 2개 1개 2개 / 3개 2개 3개 / 4 3 4 / 5 4 5 / ... 처럼 반복된다.

각 3개의 줄을 묶어서, 1섹션(1~3줄), 2섹션(4~6줄), 3섹션(7~9줄)이라고 해도 되지만,

나는 1섹션(1~2줄), 2섹션(3~5줄), 3섹션(6~8줄), 4섹션(9~11줄).. 이라고 편의상 정했다.

이렇게 되면, 1 0 / 1 2 1 / 2 3 2 / 3 4 3 / 4 5 4 / 5 6 5 / .... 와 같이 반복된다고 생각하면 된다.

 

두 번째 규칙은, 각 섹션에서 민트초코가 시작하는 칸이 몇 번째 칸인지.

각 섹션에서, 첫번째 줄은 첫 번째 칸부터, 두번째 줄은 3번째 칸부터, 세번째 줄은 2번째 칸부터 민트초코가 나오기 시작한다.

 

---

 

그렇다면 이제 n번째 민트초코가 몇번째 칸에 존재하는 지 구해 보자.

우선, 각 섹션에 존재하는 민트초코의 개수를 일반화할 수 있다.

(k번째 Section에 존재하는 민트초코의 개수) = (3k-2) 라고 할 수 있으므로,

(k번째 Section까지 존재하는 총 민트초코의 개수) 는 아래와 같다.

따라서 이를 이용하여, 이분 탐색으로 n번째 민트초코가 몇 번째 Section에 포함되어 있는 지 알아낼 수 있다.

(line 32~43)

 

그 이후는 간단하다.

k줄까지의 초콜릿 개수는 k(k+1)/2 이므로, 직전 Section까지의 초콜릿 개수를 제외해준 다음,

Section 내에서 첫번째 줄인지, 두번째 줄인지, 세번째 줄인지에 따라 알맞게 처리해주면 된다.

(line 45~58)

 

#include <algorithm>
#include <iostream>
#include <vector>
#define init cin.tie(0)->ios_base::sync_with_stdio(0);

typedef long long ll;
const ll MAX = 1e16 + 10;

using namespace std;

vector<ll> result;

int main() {
    init;

    ll a = 1;
    ll d = 3;

    int T;
    ll n;
    cin >> T;
    for (int k = 0; k < T; k++) {
        cin >> n;

        if (n == 1) {
            result.push_back(1);
            continue;
        }

        ll section = 0;

        ll lo = 0, hi = ll(1e9);
        while (lo <= hi) {
            ll mid = (lo + hi) / 2;
            ll S = mid * (3 * mid - 1) / 2;

            if (S >= n) {
                section = mid;
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }

        ll p = section - 1;
        n -= p * (3 * p - 1) / 2;

        ll line = 2 + (section - 2) * 3;

        ll total = (1 + line) * line / 2;

        if (n <= section - 1) {
            total = total + 2 + (n - 1) * 3;
        } else if (n <= section * 2 - 1) {
            total = total + (line + 1) + 1 + (n - (section - 1) - 1) * 3;
        } else {
            total = total + (line + 1) + (line + 2) + 3 + (n - (section * 2 - 1) - 1) * 3;
        }

        result.push_back(total);
    }

    for (int k = 0; k < result.size(); k++) {
        cout << result[k] << "\n";
    }
}