백준 28257번 : 알록달록 초콜릿 만들기(C/C++)

<문제>

백준 28257번

 

<풀이>

공식 해설을 참고하여 작성된 풀이입니다.

 

n번째 민트 초코는 어떤 수인지 구하는 문제이다.

브루트 포스는 당연히 시간 초과가 날 것이다.

규칙을 찾기위해 R번째 줄에 몇개의 민트 초코가 있는지 고찰해보면

줄마다 1, 0, 1 / 2, 1, 2 / 3, 2, 3 / 4, 3, 4 개의 민트초코가 있다는 사실을 알 수 있다.

 

3k번째 줄까지의 민트 초코의 개수를 살펴보면 등차 수열의 합이다.

이분탐색을 이용하여 n <= k(3k+1)/2 를 만족하는 k값의 최소를 찾아주면 된다.

 

 

/k, k-1, k/ 의 규칙을 이용해서 구체적으로 몇번째 줄(line), 몇번째 칸(b)에 있는지 구해준뒤

값을 출력해주면 된다.

 

자세한 풀이는 아래 코드를 참고.

 

<구현>

#include<bits/stdc++.h>
#define fio()                     \
    ios_base::sync_with_stdio(0); \
    cin.tie(0)
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
typedef tuple<int, int, int> tpi;
typedef tuple<ll, ll, ll> tpl;
typedef pair<double, ll> pdl;
 
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int dx[] = { 0, 1, 0, -1 };
const int dy[] = { 1, 0, -1, 0 };
const double pi = acos(-1);
const int MOD = 1000000007;
 
int main(){
    int T; scanf("%d", &T);
    while(T--){
        ll n; scanf("%lld", &n);
        ll l = 1, r = INF, k = r;
        while(l <= r){
            ll mid = l+r >> 1;
            ll y = mid*(3*mid+1)/2;
            if(y < n){
                l = mid+1;
            }
            else{
                r = mid-1;
                k = min(k, mid);
            }
        }
        ll a = n-(k-1)*(3*k-2)/2;
        ll line, b;
        if(a <= k){
            line = 3*k-2;
            b = 3*a-2;
        }
        else if(a <= 2*k-1){
            line = 3*k-1;
            b = 3*(a-k);
        }
        else{
            line = 3*k;
            b = 3*(a-2*k+1) - 1;
        }
        printf("%lld \n", line*(line-1)/2 + b);
    }
}

 

질문 지적은 언제든 환영입니다~