백준 3655 - 먼저 가세요

 

 

문제 설명

상근이는 친구들과 함께 라인제로 스키장에 왔다. 오전, 오후에는 열심히 스키를 타고, 저녁 때는 근처 바로 가서 술을 마시며 친구들과 놀려고 한다.

라인제로 스키장은 모든 시설이 세계 최고를 자랑하지만, 한 가지 단점이 있다. 바로, 스키 리프트이다. 리프트는 너무 작아서 5초에 한 명씩 태울 수 있다.

보통 친구와 동시에 스키장의 정상에서 내려온다고 해도, 리프트가 있는 곳에는 동시에 도착하지 않는다. 따라서, 리프트를 타기 전에 친구가 내려오기를 기다려야 하고, 리프트에서 내린 이후에도 친구가 내리기를 기다려야 한다.

상근이는 친구가 아직 리프트에 도착하지 않았다면, 줄을 뒤에 있는 사람에게 양보하려고 한다. 상근이의 입장에서 이 상황을 살펴 보면, 상근이가 아낄 수 있는 시간은 없고, 기다리는 장소의 차이만 있을 뿐이다. 하지만, 상근이가 양보한 사람의 관점에서 보면 그 사람이 속한 그룹은 기다리는 시간을 아낄 수 있다. 예를 들어, 그 사람의 친구가 이미 리프트에서 내려서 그 사람을 기다리고 있다고 하면, 그 사람의 친구는 기다리는 시간을 절약하게 된다.

상근이는 모든 사람이 위와 같은 행동을 한다면, 많은 사람들이 기다리는 시간을 절약할 수 있다고 생각한다. 

어떤 사람이 줄을 양보했을 때, 자신이 아끼는 시간은 없지만, 다른 사람이 아끼는 시간이 생긴다면 줄을 양보한다고 가정하자. 더 이상 이 행동을 할 수 없을 때까지 반복했을 때, 총 아낄 수 있는 시간을 얼마나 되는지 구하는 프로그램을 작성하시오.

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, 같은 그룹에 인원이 모두 리프트에 도착해야 출발할 수 있다.

따라서, 순서를 적절히 양보해서 모든 인원이 기다리는 시간을 줄였을 때 줄일 수 있는 시간을 구해야 한다.

 

문제를 이해하는 것이 살짝 어려운 문제였다.

간단한 예를 들어 보자.

AABABB

위와 같은 상황에서 제일 앞에 있는 B가 그 뒤에 있는 A에게 양보를 한다면 "AAABBB"가 된다.

그렇게 되면 앞에 있던 두 개의 A는 제일 뒤에 있는 A를 기다리는 시간이 각각 5초씩 줄게 된다.

제일 앞에 있는 B는 어차피 마지막 B를 기다려야 하기 때문에 기다리는 시간이 달라지지 않는다.

따라서, 위와 같이 바꾼다면 앞에 있는 A가 5초씩 총 10초가 줄며 제일 뒤에 있는 A 역시 5초를 덜 기다려도 되기 때문에 총 15초를 줄일 수 있다.

 

그럼 조금 더 복잡한 상황을 생각해 보자.

Ab9AAb2bC2

우선, 앞에 있는 Ab는 모두 자신의 그룹을 기다려야 한다.

하지만, 9는 혼자이기 때문에 바로 리프트를 탈 수 있다.

따라서, Ab가 9에게 양보한다면 9는 10초를 아낄 수 있다.

앞선 경우와 마찬가지로 Ab는 어차피 같은 그룹을 기다려야 하기 때문에 기다리는 시간은 변하지 않는다.

9AbAAb2bC2

위와 같은 상황에서 제일 앞에 있는 b가 뒤에 있는 AA에게 자리를 양보하면 제일 앞에 있는 A는 5초를 b뒤에 있는 AA 역시 5초를 줄일 수 있다.

즉, A그룹은 총 15초를 줄일 수 있다.

9AAAbb2bC2

이제, bb뒤에 있는 2가 제일 뒤에 있는 b에게 양보할 수 있다.

그렇다면 앞에 bb는 각각 5초씩 제일 뒤에 있는 b 역시 5초, 총 15초를 줄일 수 있다.

9AbAAbb2C2

앞에 9와 마찬가지로 C는 혼자이기 때문에 그 앞에 있는 2에게 양보한다면 5초를 줄일 수 있다.

9AbAAbbC22

 

정리하면, 9는 10초, A는 15초, b도 15초, C는 5초로 총 45초를 줄일 수 있다.

 

그렇다면 위와 같은 경우를 어떻게 구현해야 하는지 생각해 보자.

해당 문제에서 중요한 요소는 같은 그룹 중 가장 뒤에 있는 사람의 인덱스가 중요하다.

Ab9AAb2bC2

마지막 요소의 인덱스를 정리하면 다음과 같다.

그룹	마지막 인덱스
9	2
A	4
b	7
C	8
2	9

이것이 의미하는 것은 각 그룹이 최종적으로 기다려야 하는 시간이 된다.

A는 아무리 앞에서 빨리 나오더라도 결국 4번 인덱스까지는 기다려야 된다는 얘기이다.

즉, 마지막 인덱스가 빠른 그룹을 우선으로 리프트를 태운다고 하면 전체의 시간을 줄이기 유리하다.

따라서, 각 그룹의 마지막 인덱스를 입력 시에 계산해서 그를 기준으로 정렬하면 최종 상태를 얻을 수 있다.

//초기
Ab9AAb2bC2
//최종
9AAAbbbC22

최종 상태를 구했다면 초기 상태에서 그룹의 마지막 인덱스에서 얼마큼 앞으로 당겨졌는지 계산하면 된다.

이는 모든 그룹원에게 적용되는 것이기 때문에 그룹의 인원수를 곱해주어야 한다.

9는 2에서 0으로 2칸이 당겨졌으므로 2 * 5 * 1= 10

A는 4에서 3으로 당겨졌으므로 1 * 5 * 3 = 15

b는 7에서 6으로 당겨졌으므로 1 * 5 * 3 = 15

C는 8에서 7로 당겨졌으므로 1 * 5 * 1 = 5

2는 변함이 없다.

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>

using namespace std;

int T, N;

struct Group
{
    Group(char n, int idx) :
        name(n), lastIndex(idx) {};

    char name;
    int lastIndex;

    bool operator < (const Group& Other)
    {
        return lastIndex < Other.lastIndex;
    }
};

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout << fixed;
    cout.precision(4);

    //9AAAbbbC22
    cin >> T;

    while (T--)
    {
        cin >> N;

        vector<char> people(N);
        map<char, int> peopleCnt;
        map<char, int> lastIdx;

        for (int i = 0; i < N; i++)
        {
            cin >> people[i];
            peopleCnt[people[i]]++;
            lastIdx[people[i]] = i;
        }

        vector<Group> groups;
        for (int i = 0; i < N; i++)
        {
            groups.push_back(Group(people[i], lastIdx[people[i]]));
        }

        sort(groups.begin(), groups.end());

        int ans = 0;
        for (int i = 0; i < N; i++)
        {
            char current = groups[i].name;
            int groupCnt = peopleCnt[current];

            int lastGroupIdx = i + groupCnt - 1;
            i = lastGroupIdx;

            ans += 5 * (lastIdx[current] - lastGroupIdx) * groupCnt;
        }

        cout << ans << "\n";
    }


    return 0;
}

---