BOJ 1011

백준 1011, Math + Observation

$1 + 2 + 3 + \cdots + (i-1) + i + (i-1) + \cdots + 2 + 1 = i^2$
위 관계를 생각을 해야 풀 수 있는 문제다.
처음에는 prefix sum 으로 접근을 했으나 풀 수가 없었다.

$1 + 2 + 3 + \cdots + (i-1) + (i-1) + \cdots + 2 + 1 = i(i-1)$
$1 + 2 + 3 + \cdots + (i-1) + i + i + (i-1) + \cdots + 2 + 1 = i(i+1)$
임을 관찰하여 푼 방법이 눈에 띄었다.

ceil() 을 이용해서 푸는 방법도 있고,
zagabi의 방법처럼 compact 하게 푸는 방법도 있다.
PS는 배울수록 오묘하다.

Source Code

1011링크

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

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;

#define ll long long

#define pii pair<int, int>
#define pll pair<ll, ll>
#define MAXI 1000000000
#define cplx complex<double>
#define MOD 9901
const double PI = acos(-1);
const ll INF = INT_MAX / 4;

int T;
// https://kbj96.tistory.com/34
ll solve(ll d){
    ll ans = 0;
    for (ll i = 1; i < 66000; ++i){
        if(i*(i-1) < d && d <= i*i){
            ans = 2 * i - 1;
            break;
        }
        if (i *i < d && d <= i * (i+1)) {
            ans = 2 * i;
            break;
        }
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> T;

    while(T--){
        ll s, e;
        cin >> s >> e;
        printf("%lld\n", solve(e - s));
    }
}

/*
//zagabi's solution
#include <cstdio>

int main() {
    int t, a, b;
    scanf("%d", &t);

    while (t--) {
        scanf("%d %d", &a, &b);
        b -= a;

        int cnt = 0, i = 1;
        for (; b > i * 2; i++, cnt += 2) b -= i * 2;
        cnt += (b / i);
        if (b % i) cnt++;
        printf("%d\n", cnt);
    }
}

//solution using ceil()
//http://wookje.dance/2018/03/25/boj-1011-Fly-me-to-the-Alpha-Centauri/
#include <math.h>
#include <stdio.h>

int main() {
    int tc;
    for (scanf("%d", &tc); tc; tc--) {
        int s, e;
        scanf("%d %d", &s, &e);

        long long i = 1, d = e - s;
        while (i*i <= d) i++; i--;
        d = ceil((double)(d-i*i)/i);

        printf("%lld\n", i+i-1+d);
    }
    return 0;
}



*/

PREVIOUSBOJ 1029

NEXTBOJ 14488