백준 16678 - 모독 (C++)

 

 

문제 이해가 처음에 다소 헷갈리는 부분이 있었다.

 

먼저, Defile 프로젝트는 위의 설명과 같다.

모든 국회의원의 명예를 1씩 감소시키고, 0이 된 국회의원이 있다면 해당 국회의원을 파면한다.

이 과정을 반복하며 모든 국회의원을 박탈하는 것이 목표이다.

 

다만, 해커를 이용한 명예 실추가 본인은 Defile프로젝트의 1번 과정과 관련이 있는 건가 싶었는데, 이는 일종의 사전작업이라고 생각하면 될 듯하다.

 

경우에 따라 Defile 프로젝트를 실행하더라도, 모든 국회의원을 파면할 수 없을 수도 있다. 이런 상황을 방지하기 위해, 해커를 이용해 명예를 미리 감소시켜놓는 것이다.

 

즉, Defile 프로젝트를 성공시키기 위해 해커를 이용해 사전 작업을 한다고 가정했을 때, 해커를 최소 몇 명을 고용해야 하는가? 를 구하는 문제이다.

 

문제 풀이

먼저, Defile프로젝트를 성공시키기 위한 조건을 생각해보자.

 

조건을 보면, 모든 국회의원의 명예를 1씩 실추시킨 뒤, 파면되는 국회의원이 없다면 해당 프로젝트는 종료된다.

즉, 첫 시도에서 적어도 1명 이상의 국회의원이 파면되어야 한다는 것이다.

=> 명예가 1인 국회의원이 적어도 1명 있어야 한다.

 

또한, 첫 번째 시도만 성공해야 하는 것이 아니라 매 시도마다 파면되는 국회의원이 반드시 1명은 있어야 한다.

(1명도 없는 순간에는 프로젝트가 종료되기 때문에)

 

생각해보면, 모든 국회의원의 명예를 1씩 실추하게 되면, 1인 국회의원은 명예가 0이 되므로 파면될 것이다.

그렇다면 그 다음 시도에서 파면될 국회의원은? 1이 실추된 이후에 남은 명예가 1인 국회의원일 것이다.

 

즉, 처음 명예가 2인 국회의원이 두 번째 시도에서 파면될 것이다.

 

이 논리를 반복적으로 이어가보면, 명예가 1인 국회의원이 처음 파면되고 그 다음엔 명예가 2인 국회의원이 파면되며 그 다음엔 명예가 3인 국회의원이 파면되고 이 과정이 반복될 것이다.

 

즉, 모든 국회의원을 명예 순으로 정렬했을 때 이전 국회의원의 명예와 2이상 차이가 나는 국회의원이 없어야 한다는 것이다.

(한 국회의원을 파면한 이후에 파면되는 국회의원은 파면된 국회의원의 명예보다 1만큼 큰 명예를 가진 국회의원이므로)

 

그러므로, 해커를 이용해 맞추어야할 사전 작업은 아래와 같다.

 

1. 모든 국회의원중 1의 명예를 가진 국회의원이 적어도 1명 존재해야 한다.

2. 모든 국회의원을 명예 기준으로 오름차순 정렬했을 때, 어떤 국회의원의 명예가 앞의 국회의원과 2이상 차이가 나서는 안된다.

 

하나의 예시를 보자.

7 3 6 2 4

 

국회의원의 명예가 위와 같이 입력되었다고 해보자.

이를 오름차순으로 정렬하면, 2 3 4 6 7 이 된다.

 

반드시, 명예가 1인 국회의원이 1명은 존재해야 하므로 해커를 이용해 맨 앞의 국회의원의 명예를 1을 실추시켜야 한다.

-> Hacker 1명 고용 

-> 명예 : 2 3 4 6 7 -> 1 3 4 6 7 로 변경

 

모든 국회의원은 앞의 국회의원의 명예보다 2이상 큰 명예를 지녀선 안된다.

두 번째 국회의원부터 명예를 실추해보자.

 

첫 번째 국회의원의 명예가 1이므로, 두 번째 국회의원의 명예는 최대 2까지 보유할 수 있다.

->Hacker 1명 고용

-> 명예 : 2 3 4 6 7 -> 1 2 4 6 7 로 변경

 

두 번째 국회의원의 명예가 2이므로 세번째 국회의원의 명예는 최대 3까지 보유할 수 있다.

->Hacker 1명 고용

-> 명예 : 1 2 4 6 7 -> 1 2 3 6 7 로 변경

 

세 번째 국회의원의 명예가 3이므로 네 번째 국회의원의 명예는 최대 4까지 보유할 수 있다.

->Hacker 2명 고용

-> 명예 : 1 2 3 6 7 -> 1 2 3 4 7 로 변경

 

네 번째 국회의원의 명예가 4이므로 다섯 번째 국회의원의 명예는 최대 5까지 보유할 수 있다.

->Hacker 2명 고용

-> 명예 : 1 2 3 6 7 -> 1 2 3 4 5 로 변경

 

총 7명의 해커를 고용하여 모든 조건은 만족시키도록 하였다.

이 상태에서 defile 프로젝트를 실행하게 되면 아래와 같은 과정을 거치며 모든 국회의원의 명예를 실추할 수 있다.

 

첫 명예 : 1 2 3 4 5

1번째 시도 : 0 1 2 3 4

2번째 시도 : 0 0 1 2 3

3번째 시도 : 0 0 0 1 2

4번째 시도 : 0 0 0 0 1

5번째 시도 : 0 0 0 0 0

 

이처럼 7명의 해커를 이용해 미리 명예를 실추해놓으면, 1번의 Defile 프로젝트를 통해 모든 국회의원을 파면할 수 있다.

 

코드 풀이

int NumOfMan = 0;
std::cin >> NumOfMan;

std::vector<int> Honors(NumOfMan, 0);
for (int i = 0; i < NumOfMan; i++)
{
    std::cin >> Honors[i];
}

 

먼저, 국회의원의 수와 명예를 입력받는다.

std::sort(Honors.begin(), Honors.end());

 

이후, 명예를 오름차순으로 정렬한다.

long long HackerCount = Honors[0] - 1;
Honors[0] = 1;

 

 

해커를 고용하여 가장 작은 명예를 1로 맞춰준다.

참고로, 국회의원은 최대 10만명이고 명예는 최대 10만이므로 HackerCount의 최대값은 int범위를 초과한다.

그러므로 long long 자료형으로 선언해주어야한다.

for (int i = 1; i < NumOfMan; i++)
{
    int CurHonor = Honors[i - 1] + 1;

    if (Honors[i] > CurHonor)
    {
        int Gap = Honors[i] - CurHonor;
        HackerCount += Gap;
        Honors[i] = CurHonor;
    }
}

 

반복문을 돌며, 이전 인덱스의 명예보다 2 이상 차이나지 않도록 갱신해주었다.

그 과정에서 명예를 깎는 만큼 HackerCount를 증가시켜주었다.

std::cout << HackerCount;

return 0;

 

마지막으로 HackerCount를 출력해주면 끝이다.

 

코드 전문

#include <iostream>
#include <vector>
#include <algorithm>

void Init()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
}

int main()
{
    Init();

    int NumOfMan = 0;
    std::cin >> NumOfMan;

    std::vector<int> Honors(NumOfMan, 0);
    for (int i = 0; i < NumOfMan; i++)
    {
        std::cin >> Honors[i];
    }

    std::sort(Honors.begin(), Honors.end());

    long long HackerCount = Honors[0] - 1;
    Honors[0] = 1;

    for (int i = 1; i < NumOfMan; i++)
    {
        int CurHonor = Honors[i - 1] + 1;
        
        if (Honors[i] > CurHonor)
        {
            int Gap = Honors[i] - CurHonor;
            HackerCount += Gap;
            Honors[i] = CurHonor;
        }
    }

    std::cout << HackerCount;

    return 0;
}