[C++] BOJ 2456번: 나는 학급회장이다

학교에서 진행하는 수업에서 공유받은 알고리즘 문제를 풀어보았다. 문제의 난이도는 브론즈 1으로, 쉬울 것으로 예상하고 문제를 풀었으나 예상보다 코드가 길어지고 3번째 제출에서야 '맞았습니다!!'가 출력되어 브론즈 1 난이도 치고는 어려웠다. 개인적으로는 실버 난이도가 조금 더 적절하다고 생각이 든다.

문제 링크

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

문제 분석

3명의 후보 중 가장 큰 점수를 받은 후보가 단 한 명인 경우에는 문제가 단순해지지만, 여러 명인 경우에는 조건문을 통해 확인해야 하는 조건이 많아져 코드가 길어지는 문제이다. 이 문제에서 조건문을 유심히 처리해야 하는 내용은 아래에 작성된 문제의 조건이다.

점수가 가장 큰 후보가 여러 명인 경우에는 3점을 더 많이 받은 후보를 회장으로 결정하고, 3점을 받은 횟수가 같은 경우에는 2점을 더 많이 받은 후보를 회장으로 결정한다. 그러나 3점과 2점을 받은 횟수가 모두 동일하면, 1점을 받은 횟수도 같을 수밖에 없어 회장을 결정하지 못하게 된다.

문제 풀이

int score_sum[4];

int main(void)
{
    int N;

    cin >> N;

    while (N--)
    {
        for (int i = 1; i <= 3; i++)
        {
            int value;
            cin >> value;
            score_sum[i] += value;
        }
    }

    int max_index = 1;
    int max_score = score_sum[1];

    // 최고 점수를 받은 후보와 최고 점수 계산
    for (int i = 1; i <= 3; i++)
    {
        if (max_score < score_sum[i])
        {
            max_score = score_sum[i];
            max_index = i;
        }
        else if (max_score == score_sum[i])
        {
            max_index = i;
        }
    }

    cout << max_index << " " << max_score << '\n';

    return 0;
}

먼저 위와 같이 입력을 받고, 각 후보 별로 입력받은 점수들의 합을 계산한다. 그리고 최고 점수를 받은 후보가 몇 번인지와, 최고 점수를 계산한다. 위와 같이 코드를 작성해주면 최고 점수를 받은 후보가 한 명인 경우에 대해서는 적절한 결과를 출력하게 된다.

else if (max_score == score_sum[i])
{
    max_index = i;
}

이 때, 위와 같이 max_score의 점수와 score_sum[i]의 점수가 같을 때 max_index의 값을 바꾸어주는 이유는 최고 점수를 받은 후보가 여러 명인 경우 max_index가 더 큰 번호의 후보를 가리키도록 하기 위함이다.

 

이제 여기서 최고 점수를 받은 후보가 여러 명인 경우까지 처리하기 위해 코드를 추가해주자.

int added_score[4][4]; // added_score[점수][학생]

while (N--)
{
    for (int i = 1; i <= 3; i++)
    {
        int value;
        cin >> value;
        score_sum[i] += value;
        added_score[value][i] += 1;
    }
}

먼저 각 후보가 3점, 2점, 1점을 몇 번 받았는지 확인하기 위해 added_score[value][i] 배열을 추가해준다. 그리고 입력을 받을 때 for문 내에서 added_score[value][i] 값을 계산해준다.

 

위의 방식대로 구현하면 added_score 배열을 통해 학생 후보가 특정 점수를 받은 횟수를 확인할 수 있다. 예를 들어 added_score[3][1]에 접근할 경우 1번째 학생이 3점을 받은 횟수를 읽어오게 된다.

 

그리고 다음으로 3점을 더 많이 받은 사람을 후보로 정하고, 만약 3점의 횟수가 동일한 경우 2점을 많이 받은 사람을 후보로 정하고, 2점을 받은 횟수마저 같은 경우 후보가 없도록 하는 코드를 작성해주자.

for (int i = 1; i <= 3; i++)
{
    if (max_index == 0)
        break;
    if (max_index == i)
        continue;
    if (score_sum[i] == max_score)
    {
        if (added_score[3][i] > added_score[3][max_index])
        {
            max_index = i;
        }
        else if (added_score[3][i] == added_score[3][max_index])
        {
            if (added_score[2][i] > added_score[2][max_index])
                max_index = i;
            else if (added_score[2][i] == added_score[2][max_index])
                max_index = 0;
        }
    }
}

코드를 작성하면 다음과 같다. if 문이 여러 번 중첩된다.

전체 코드

위의 작업을 종합해 작성한 전체 코드는 다음과 같다.

#include <iostream>
#include <vector>

using namespace std;

int score_sum[4];
int added_score[4][4]; // added_score[점수][학생]

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;

    cin >> N;

    while (N--)
    {
        for (int i = 1; i <= 3; i++)
        {
            int value;
            cin >> value;
            score_sum[i] += value;
            added_score[value][i] += 1;
        }
    }

    int max_index = 1;
    int max_score = score_sum[1];

    for (int i = 1; i <= 3; i++)
    {
        if (max_score < score_sum[i])
        {
            max_score = score_sum[i];
            max_index = i;
        }
        else if (max_score == score_sum[i])
        {
            max_index = i;
        }
    }

    for (int i = 1; i <= 3; i++)
    {
        if (max_index == 0)
            break;
        if (max_index == i)
            continue;
        if (score_sum[i] == max_score)
        {
            if (added_score[3][i] > added_score[3][max_index])
            {
                max_index = i;
            }
            else if (added_score[3][i] == added_score[3][max_index])
            {
                if (added_score[2][i] > added_score[2][max_index])
                    max_index = i;
                else if (added_score[2][i] == added_score[2][max_index])
                    max_index = 0;
            }
        }
    }

    cout << max_index << " " << max_score << '\n';

    return 0;
}

 

결과