[BOJ/Silver 4] 백준 27919 UDPC 파티(C++)

문제 링크

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

27919번: UDPC 파티

 

문제

윤이, 포닉스, 달구는 UDPC가 열리는 것을 기념해 한 장소에 모여 파티를 열기로 했다! 수많은 참가자와 함께 즐거운 시간을 보내던 중, 참가자들이 세 마스코트 중 누가 제일 귀여운지 토론하기 시작했다.

 

UNIST 마스코트 '윤이' - 출처: 윤찐빵

야, 아무리 봐도 우리 윤이가 제일 귀엽지. 앙증맞은 뿔과 매력적인 갈기 좀 봐!

 

POSTECH 마스코트 '포닉스' - 출처: POSTECH 홈페이지

그렇게 치면 우리 포닉스의 갈기는! 귀여운 날개랑 꼬리도 가지고 있지~

 

DGIST 마스코트 '달구' - 출처: 주식회사 테라핀 홈페이지

어차피 우리 달구가 제일 귀엽죠? 이목구비는 물론이고 통통한 몸과 붕어빵마저 귀엽잖아!

 

토론은 끝날 기미가 없었고, 말하다 지친 참가자들은 누가 제일 귀여운지 투표하기로 했다. 참가자는 종이에 U, D, P, C 중 하나만 적어 투표함에 넣었고, 각각 윤이, 달구, 포닉스, 기권을 의미한다. 한 마스코트가 받은 표의 수가 다른 두 마스코트가 각각 받은 표의 수보다 모두 크다면 그 마스코트가 제일 귀여운 마스코트로 선정된다!

투표가 모두 끝나 세 마스코트가 개표를 시작했다. 그런데 글씨체와 방향이 제각각이라 종이에 적힌 알파벳이 서로 비슷하게 생긴 U와 C, 그리고 D와 P 중 무엇인지 알 수 없어 개표 결과가 엉망이 되었다!

 

U일까 C일까? 정답은 UUUU!

D일까 P일까? 정답은 DPDP!

 참가자가 투표한 결과가 주어질 때, 세 마스코트가 개표할 때 U와 C, D와 P가 서로 바뀔 수 있는 것을 고려하여, 누가 제일 귀여운 마스코트로 선정될 수 있을지 알아내자.

 

입력

첫 번째 줄에 참가자가 투표한 결과 V가 주어진다. V는 U, D, P, C만 포함하는 문자열이고, 길이는 0보다 크고 100,000을 넘지 않는다.

 

출력

윤이가 선정될 수 있다면 U, 달구가 선정될 수 있다면 D, 포닉스가 선정될 수 있다면 P를 출력한다.

선정될 수 있는 모든 마스코트의 알파벳을 위 순서대로 출력한다.

만약 U, D, P 중 어느 것도 출력하지 않는다면 C를 출력한다.

 

예제 입력 1

UDPC

예제 출력 1

UDP

예제 입력 2

UDP

예제 출력 2

DP

 

알고리즘 분류

• 그리디 알고리즘

 

풀이

우선 D나 P가 하나라도 있다면 둘 다 D나 P가 될 수 있으므로 D와 P의 최대 득표 수는 일치하며, U가 있건 없건 전부 C로 간주할 수 있으므로 D, P 둘 다 가장 귀여운 마스코트로 선정될 수 있다.

U나 C가 등장한다면 전부 U로 간주할 수 있는데, 여기서 D, 혹은 P의 최대 득표 수가 짝수라면 그 절반의 수보다 U의 최대 득표 수가 커야 U가 가장 귀여운 마스코트로 선정될 수 있고, D/P의 최대 득표 수가 홀수라면 그 절반의 수 + 1보다 U의 최대 득표 수가 커야 U가 가장 귀여운 마스코트로 선정될 수 있다. 왜냐하면 D/P의 총 득표 수를 D, P가 최대한 차이가 나지 않게 나누어 가지려면 총 득표 수를 절반으로 나누는 방법이 최선이기 때문이다.

마지막으로 선정될 수 있는 모든 마스코트를 U, D, P 순으로 출력하고, 만약 선정될 수 있는 마스코트가 존재하지 않는다면 C를 출력한다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
string V;
int U, D, P, C, M;
string Answer;

void input() {
    cin >> V;
}

void settings() {
    for (int i = 0; i < (int)V.length(); i++) {
        if (V[i] == 'U') {
            U++;
            C++;
        }
        else if (V[i] == 'C') {
            U++;
            C++;
        }
        else {
            P++;
            D++;
        }
    }
    if (D % 2 == 0) {
        if (U > (D / 2)) {
            Answer += "U";
        }
    }
    else {
        if (U > (D / 2) + 1) {
            Answer += "U";
        }
    }
    if (D > 0) {
        Answer += "D";
        Answer += "P";
    }

    if (Answer == "") {
        Answer += "C";
    }
}

void find_Answer() {
    cout << Answer << "\n";
}

int main() {
    FASTIO
    input();
    settings();
    find_Answer();

    return 0;
}