[ 백준 ] 1292 / 쉽게 푸는 문제

金弘均·2021년 9월 15일
0

Baekjoon Online Judge

목록 보기
55/228
post-thumbnail

# Appreciation

/*
 * Problem :: 1292 / 쉽게 푸는 문제
 *
 * Kind :: Math
 *
 * Insight
 * - 수열을 만드는 것은 좀 아닌 것 같다
 *   + 길이가 1000*(1000+1)/2 이니
 *     만들어서 풀어도 상관없을 것 같긴 한데
 *     n*(n+1)/2 하면 될 것을 1+2+...+100 하는 느낌이라
 *     좀 비효율적일 것 같다
 *     # 첫번째 원소의 인덱스를 0 이라 하면
 *       1 : [0, 1)   => [0, 0] / 1*2/2 = 1
 *       2 : [1, 3)   => [1, 2] / 2*3/2 = 3
 *       3 : [3, 6)   => [3, 5] / 3*4/2 = 6
 *       4 : [6, 10)  => [6, 9] / 4*5/2 = 10
 *       5 : [10, 15) => [10, 14] / 5*6/2 = 15
 *       ...
 *       위 규칙에 따라 숫자 n 의 해당하는 구간의 인덱스를 쉽게 알 수 있다!
 *       -> 숫자 n 이 구간 A, B 에 몇 개 들어있는지 알아내 이를 모두 더해주자!
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>

using namespace std;

#define endl '\n'

// Set up : Global Variables
/* None */

// Set up : Functions Declaration
/* None */


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    int A, B;
    cin >> A >> B;

    // Process
    A--, B--; /* 첫 번째 원소의 인덱스가 0 임에 따른 해당 구간의 인덱스 보정 */
    int n = 1; /* 현재 구간 숫자 */
    int ans = 0;
    while (true) {
        int li = (n-1)*n/2; /* 현재 구간 왼쪽 인덱스 */
        int ri = n*(n+1)/2-1; /* 현재 구간 오른쪽 인덱스 */
        /*  n ... n
         * li    ri */
        /* ri 가 A 보다 작으면 현재 구간은 해당 구간에 포함되지 않음 */
        if (ri < A) { n++; continue; }
        /* li 가 B 보다 크면 현재 구간 및 이후 구간은 해당 구간에 포함되지 않음 */
        if (li > B) break;
        int sli = max(A, li); /* 해당 구간에 포함되는 현재 구간의 왼쪽 인덱스 */
        int sri = min(B, ri); /* 해당 구간에 포함되는 현재 구간의 오른쪽 인덱스 */
        ans += (sri-sli+1)*n++;
    }

    // Control : Output
    cout << ans << endl;
}

// Helper Functions
/* None */
profile
이런 미친 게임을 봤나! - 옥냥이

0개의 댓글