[백준] 16678 - 모독

1. 문제

16678번: 모독

2. 개요

국회의원 N명이 있고 이들은 각각의 명예 점수를 가지고 있다.

이들은 명예 점수가 0이 되면 국회의원직을 박탈당한다.

왕은 다음과 같은 Defile 프로젝트를 수행하여 이들을 퇴진시키려고 한다.

1. 모든 국회의원을 모독해서 각각의 명예 점수를 1씩 감소시킨다.
2. (1)로 인해 1명이라도 국회의원에서 박탈당한 사람이 발생했다면 국민들의 분노를 이용해 (1)로 돌아간다.
3. (1)에 의해 국회의원에서 박탈당한 사람이 없다면 프로젝트를 종료한다.

단 한 번의 프로젝트로 모든 국회의원을 쫒아내려고 한다.

사전에 해커를 고용해 명예를 깎아놓으려고 한다. 해커 한 명당 국회의원 한명의 명예를 1 깎을 수 있다. 이 때 필요한 최소 해커의 수를 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

국회의원의 명예점수를 1부터 시작하여 인접한 수의 차이가 1이하가 되도록 하는 오름차순으로 만들면 된다.

목표를 1로 설정하고 명예가 가장 적은 의원부터 시작한다.

목표보다 현재 명예가 더 적다면 건너뛰고, 그렇지 않다면 명예를 깎아내리고 그 차이만큼 답을 증가시킨다. 거기에 목표를 1만큼 늘려준다.

모든 국회의원에 대해 작업을 마쳤다면 답을 출력한다.

3-2. Python

import sys

N = int(sys.stdin.readline())

answer = 0
honors = []

for i in range(N):
    honors.append(int(sys.stdin.readline()))

honors.sort()

todo = 1
for i in range(N):
    if honors[i] >= todo:
        answer += honors[i] - todo
        honors[i] = todo
        todo += 1

print(answer)

3-3. C#

namespace boj_16678
{
    internal class Program
    {
        static void Main(string[] args)
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

            int N = int.Parse(sr.ReadLine());

            int[] honors = new int[N];

            for (int i = 0; i < N; i++)
                honors[i] = int.Parse(sr.ReadLine());

            Array.Sort(honors);

            int todo = 1;
            long answer = 0;

            for (int i = 0; i < N; i++)
            {
                if (honors[i] >= todo)
                {
                    answer += honors[i] - todo;
                    honors[i] = todo;
                    todo++;
                }
            }

            sw.WriteLine(answer);
            sw.Close();
        }
    }
}