BOJ 11011. Forged Answer

11011번: Forged Answers (acmicpc.net)

solved.ac: Gold I (2024.09.13)

 

아이디어 하나가 필요한 그리디 문제입니다.

 

문제를 요약하면, 답지를 조작해서 세 사람의 점수 중 가장 낮은 값을 최대로 끌어올리는 문제입니다.

다음과 같이 각 문제를 분류할 수 있습니다.

• 세 사람 다 동일한 답안을 낸 경우
• 두 사람이 동일한 답안을 내고, 한 사람은 다른 답안을 낸 경우
• 세 사람 모두 다른 답안을 낸 경우

1번의 경우, 당연히 다 맞게 하는 게 최적입니다. 이는 너무나 자명합니다.

3번의 경우 원하는 사람의 점수를 1 올릴 수 있습니다.

 

2번의 경우가 조금 특이합니다. 여기서는 두 사람의 점수를 1 올리거나, 한 사람의 점수를 1 올릴 수 있습니다.

일단 솔직히 좀 난해합니다. 다음과 같이 그림을 그리겠습니다.

 

아직 3번 문제는 고려하지 않았습니다.

연보라색은 1번의 경우, 나머지는 2번의 경우이며 같은 색깔은 두 학생이 같은 제출을 내었음을 의미합니다.

 

일단 모두 두 명이 점수를 얻도록 구성하였습니다. 높이는 점수와 비례하며, 같은 색깔 블록의 높이는 동일해야 합니다.

여기서 항상 저런 꼴이 나올 수 있는 이유는, 2번 문제의 경우 학생을 고려하면 3가지 경우가 나옵니다. (1, 2), (1, 3), (2, 3)

각 문제의 개수를 a, b, c라 하면 학생을 바꿈으로써 a >= b >= c를 만들 수 있고, a + b >= a + c >= b + c이므로 항상 가능합니다.

(Without Loss Of Generality)

 

이제 약간의 케이스워크를 해 봅시다.

1. 3번 문제가 충분함

진한 보라색이 3번 문제입니다.

이 경우, 당연하게도 낮은 사람 먼저 채워주고, 나머지는 3등분하면 됩니다.

 

최댓값은 그냥 싹 더해서 3으로 나누어 주면 됩니다.

2. 약간 부족함

2번 문제에서 같은 색깔 블록 하나씩 뺀 다음에 나머지를 추가할 수는 있겠습니다만,

어떤 블록을 빼던 낮은 점수를 가진 학생의 점수가 1 감소합니다.

문제 하나를 빼서 할당할 수 있는 점수는 고작 1이기 때문에, 의미없는 행동입니다.

따라서 그냥 점수가 낮은 두 학생에 골고루 채워주면 됩니다.

 

이 경우 최댓값은 (1번 막대 + 2번 막대 + 3번 문제 수) / 2입니다.

3. 많이 부족함

이 경우, 빨간색 블록의 높이를 줄인 만큼 가장 왼쪽의 막대를 늘릴 수 있습니다.

항상 3번째 블록이 2번째 블록보단 높게 되므로, 잠시 무시하고 1번째와 2번째 막대만 관찰해 봅시다.

 

2번 막대가 1 내려가면, 1번 막대가 1 올라가게 됩니다.

어떻게 적당히 잘 맞췄다고 가정하면, 이후로는 2번의 케이스가 됩니다. 더 이상 진행하지 않아도 문제 없습니다.

따라서 이 경우 (1번 막대 + 2번 막대 + 3번 문제 수) / 2가 됩니다.

 

이제 구현 좀 해 주면 됩니다.

여담으로 2번 맞왜틀을 했는데, else if 까먹어서 틀린 거였습니다, 이런.

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int solve()
{
  int n;
  string arr[3];

  cin >> n;
  for(int i = 0; i < 3; i++) cin >> arr[i];

  int a = 0, b[3] = {0, 0, 0}, c = 0;
  for(int i = 0; i < n; i++)
    {
      if(arr[0][i] == arr[1][i] && arr[1][i] == arr[2][i]) a++;
      else
      {
        if(arr[0][i] == arr[1][i]) b[0]++;
        else if(arr[1][i] == arr[2][i]) b[1]++;
        else if(arr[2][i] == arr[0][i]) b[2]++;
        else c++;
      }
    }

  int res[3] = {a, a, a};
  for(int i = 0; i < 3; i++)
    {
      res[i] += b[i];
      res[(i + 1) % 3] += b[i];
    }
  sort(res, res + 3);

  if(res[0] + res[1] + c >= res[2] * 2)
  {
    int rem = c - (res[2] - res[1]) - (res[2] - res[0]);
    return res[2] + rem / 3;
  }
  else return (res[0] + res[1] + c) / 2;
}

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

  int T;
  cin >> T;
  while(T--)
    {
      cout << solve() << "\n";
    }
}