[ 백준 ] 2012 / 등수 매기기

金弘均·2021년 9월 15일
0

Baekjoon Online Judge

목록 보기
65/228
post-thumbnail

# Appreciation

/*
 * Problem :: 2012 / 등수 매기기
 *
 * Kind :: Sorting
 *
 * Insight
 * - 예상 등수들을 오름차순으로 정렬하고
 *   첫 번째부터 1등, 2등, 3등, ... 하면 되지 않을까?
 *   + 예상 등수들 = [1, 5, 3, 1, 2]
 *          정렬 = [1, 1, 2, 3, 5]
 *     등수 정하기 = [1, 2, 3, 4, 5]
 *          차이 = [0, 1, 1, 1, 0]
 *        차이합 = 3
 *     # 되네?
 *       아, 만약 예상 등수들이 오름차순이 아니라면
 *       차이가 같거나 더 커질 수 밖에 없구나!
 *       -> 예상 등수들 = [..., x, y, ...]
 *          등수 정하기 = [..., a, b, ...]
 *          b=a+1 이고, |x-a|+|y-b| <= |x-b|+|y-a|
 *          => x=y 라면, 위 식은 True
 *             x<y 라면,
 *               x<a,
 *                 x<y<a<b, 위 식은 True
 *                 x<y=a<b, 위 식은 True
 *                 x<a<y=b, 위 식은 True
 *                 x<a<b<y, 위 식은 True
 *             -------
 *               x=a,
 *                 x=a<y=b, 위 식은 True
 *                 x=a<b<y, 위 식은 True
 *             -------
 *               x=b,
 *                 a<x=b<y, 위 식은 True
 *             -------
 *               x>b,
 *                 a<b<x<y, 위 식은 True
 *
 * Point
 * -        N = 5*10^5,
 *   예상 등수들 = [1, 1, ..., 1, 1]
 *   등수 정하기 = [1, 2, ..., N-1, N]
 *        차이 = [0, 1, ..., N-2, N-1]
 *      차이합 = N*(N-1)/2
 *   + int 의 경우 Overflow 가 일어난다!
 *     그러니 답에 사용하는 변수는 long 자료형을 사용하자 :)
 */

# Code

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

#include <iostream>
#include <algorithm>

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 N; cin >> N;
    int A[N+1];
    for (int i=1; i<=N; i++)
        cin >> A[i];

    // Process
    long ans = 0;
    sort(A+1, A+(N+1));
    for (int i=1; i<=N; i++) {
        ans += abs(A[i]-i);
    }

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

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

0개의 댓글