백준 11011번 Forged Answers

문제 링크입니다: https://www.acmicpc.net/problem/11011

간단하게 문제 번역을 해보겠습니다.

wen, dream, moon은 기준 점수를 넘지 못해 보충 시험을 치뤄야했습니다. 

보충 시험은 객관식 시험이였습니다. 한 문제당 1점이고 사지선다형(A, B, C, D) 시험입니다.

wen, dream, moon은 시험을 다 끝내고 OMR 답안지를 제출했는데 그들의 제일 친한 친구 drazil이 그들이 전부 오답을 제출했다는 것을 알아차렸습니다.

drazil은 wen, dream, moon이 우울해하는 것을 느끼고 컴퓨터에 입력된 답을 조작하기로 마음을 먹었습니다. drazil은 세 명 중 최소 점수를 최대화시키고자 합니다. 예를 들자면, 보충 시험에 세 문제가 있었고 wen이 ABC, dream이 BCD, moon이 CDA라고 제출했고 컴퓨터에 입력된 답은 DAB였습니다. wen, dream, moon이 모두 한 문제도 못 맞췄으므로 drazil은 컴퓨터에 입력된 답을 CCC로 조작하여 친구들이 적어도 한 문제는 맞추도록 조작했습니다.

본론으로 돌아와서, wen, dream, moon이 어떤 답안을 제출했는지가 주어집니다. drazil을 도와 컴퓨터에 입력된 답을 조작해야 최소 점수를 최대화시키세요.

문제에서 핵심은 상태를 5가지로 나누는 것이였습니다.

1. wen과 dream이 동일한 답을 제출한 경우

2. wen과 moon이 동일한 답을 제출한 경우

3. dream과 moon이 동일한 답을 제출한 경우

4. 모두 동일한 답을 제출한 경우

5. 모두 다른 답을 제출한 경우

이후 알고리즘을 아래와 같습니다.

1. 1번부터 N번 문제까지 순회하면서 각각의 상태가 몇 번 등장했는지 파악합니다.

2. wen, dream, moon 기준으로 같은 문제 개수를 파악합니다.(반복문)

3. 2번에서 구한 값들을 오름차순 정렬합니다.

4. 제일 적은 경우와 중간 경우를 비교하여 전부 틀린 문제를 조작합니다.

5. 이후에는 (제일 적은 경우 + 중간 경우)와 제일 큰 경우를 비교하여 전부 틀린 문제를 조작합니다.

6. 마지막으로 전부 틀린 문제를 조작하고 제일 적은 경우를 업데이트합니다.

7. 6번에서 구한 값 + 4 번째 상태를 출력합니다.

#include <iostream>

#include <string>

#include <algorithm>

#include <cstring> //memset

using namespace std;

 

int N;

int condition[5], AC[3];

string answer[3];

 

int state(char wen, char dream, char moon)

{

        if (wen == dream && dream == moon) //동일하게 답함

                 return 4;

        if (wen == dream) //wen과 dream만 동일

                 return 0;

        if (wen == moon) //wen과 moon만 동일

                 return 1;

        if (dream == moon) //dream과 moon만 동일

                 return 2;

        if (wen != dream && dream != moon) //다 다르게 답함

                 return 3;

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0); //cin 실행속도 향상

        int test_case;

        cin >> test_case;

 

        for (int t = 0; t < test_case; t++)

        {

                 memset(condition, 0, sizeof(condition));

                 cin >> N;

                 for (int i = 0; i < 3; i++)

                         cin >> answer[i];

 

                 for (int i = 0; i < N; i++)

                         condition[state(answer[0][i], answer[1][i], answer[2][i])]++;

 

                 int result = 0;

                 //wen, dream, moon 기준으로

                 for (int i = 0; i < 3; i++)

                 {

                         for (int j = 0; j <= condition[i]; j++)

                         {

                                 int allWrong = condition[3];

                                 //같은 문제 개수 파악

                                 AC[i] = j + condition[(i + 1) % 3] + condition[(i + 2) % 3];

                                 AC[(i + 1) % 3] = condition[i] - j + condition[(i + 2) % 3];

                                 AC[(i + 2) % 3] = condition[i] - j + condition[(i + 1) % 3];

                                 //오름차순 정렬

                                 sort(AC, AC + 3);

 

                                 //전부 틀린 문제 + 제일 적은 경우 < 중간 경우

                                 //다 틀린 문제를 제일 적은 경우 위주로 조작하고 업데이트

                                 if (allWrong + AC[0] < AC[1])

                                 {

                                          AC[0] += allWrong;

                                          allWrong = 0;

                                 }

                                 //제일 적게 경우와 중간 경우가 동일한 성적을 갖도록

                                 //다 틀린 문제를 조작

                                 else

                                 {

                                          allWrong -= AC[1] - AC[0];

                                          AC[0] = AC[1];

                                 }

 

                                 //중간 경우 + 제일 적은 경우 + 다 틀린 문제 < 제일 큰 경우 * 2

                                 //다 틀린 문제를 반반 분배

                                 if (allWrong + AC[0] + AC[1] < AC[2] * 2)

                                 {

                                          AC[0] += allWrong / 2;

                                          AC[1] += allWrong / 2;

                                          allWrong = 0;

                                 }

                                 //모든 경우가 같은 성적을 갖도록 다 틀린 문제를 조작

                                 else

                                 {

                                          allWrong -= AC[2] * 2 - AC[1] - AC[0];

                                          AC[1] = AC[2];

                                          AC[0] = AC[1];

                                 }

 

                                 //다 틀린 문제를 1/3씩 분배

                                 AC[0] += allWrong / 3;

                                 result = max(result, AC[0]);

                         }

                 }

                 //result와 다 맞은 문제를 더하면 답

                 cout << result + condition[4] << "\n";

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~