[BOJ/Silver 2] 백준 28286 재채점을 기다리는 중(C++)

문제 링크

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

28286번: 재채점을 기다리는 중

 

문제

UCPC고등학교에 다니는 민규는 최근에 기말고사를 치게 되었다. 기말고사는 N문제로 이루어져 있고, 각 문제는 보기가 1 이상 5 이하의 정수로 이루어진 객관식 문제이다.

시간이 지나 학교에서 성적표를 받은 민규는 집에서 매겨본 점수보다 훨씬 낮은 점수를 받고 깜짝 놀랐다. 알고 보니 민규는 OMR 카드에 답안을 밀려 썼던 것이다. 억울하지만 어쩔 수 없이 결과를 받아들여야 했던 민규는 자신이 답안을 제대로 썼다면 얼마나 잘 봤을지라도 알아보기로 했다.

민규는 OMR 카드에 쓴 답안을 밀거나 당기는 작업을 최대 K번 할 수 있다. 답안을 한 번 밀거나 당기려면 우선 기준점이 될 문제의 번호 p를 하나 잡고, 다음 중 하나를 시행한다.

• 당기기: p번 문제의 뒤 문제들에 쓴 답안을 모두 직전 문제로 옮기고, 마지막 문제는 답안을 쓰지 않은 것으로 취급한다.
• 밀기: p번 및 그 뒤의 문제들에 쓴 답안을 모두 직후 문제로 옮기고, p번 문제는 답안을 쓰지 않은 것으로 취급한다. 마지막 문제에 쓴 답안은 버린다.

다음은 3번 문제를 기준으로 답안을 밀거나 당기는 예시이다.

문제번호	1	2	3	4	5
OMR카드 원본	1	2	4	5	1
당기기	1	2	5	1	.
밀기	1	2	.	4	5

기준점의 번호는 매 작업마다 달라도 된다.

답안을 밀거나 당기는 작업을 최대 K번 실행한 후 민규가 맞힐 수 있는 문제의 최대 개수를 구하시오. 작업을 K번보다 적게 하거나 아예 안 할 수도 있음에 유의하여라.

 

입력

첫 줄에 문제 수 N과 답안을 밀거나 당길 수 있는 최대 횟수 K가 주어진다. (5 ≤ N ≤ 20; 0 ≤ K ≤ 3)

그 다음 줄에 각 문제의 정답을 나타내는 1 이상 5 이하의 정수가 차례대로 주어진다.

그 다음 줄에 민규가 OMR 카드에 기입한 답안을 나타내는 1 이상 5 이하의 정수가 차례대로 주어진다.

 

출력

민규가 맞힐 수 있는 문제의 최대 개수를 출력한다.

 

예제 입력 1

5 0
1 2 3 4 5
1 2 4 5 1

예제 출력 1

2

예제 입력 2

5 1
1 2 3 4 5
1 2 4 5 1

예제 출력 2

4

 

알고리즘 분류

• 백트래킹

 

풀이

민규가 작성한 답안을 최대 3번까지, 1~N번 문제까지 모든 문제에서마다 답안을 당기거나 밀고 정답과 비교해서 최대 몇 문제를 맞출 수 있었는지 확인하고 맞춘 문제의 최댓값을 출력한다.

 

코드

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

using namespace std;
int N, K;
vector<int> MAP, Correct;
int Answer;

void input() {
    cin >> N >> K;
    Correct.resize(N);
    MAP.resize(N);
    for (int i = 0; i < N; i++) {
        cin >> Correct[i];
    }
    for (int i = 0; i < N; i++) {
        cin >> MAP[i];
    }
}

void DFS(int Depth, vector<int> Vec) {
    if (Depth > K) {
        return;
    }

    int Count = 0;
    for (int i = 0; i < N; i++) {
        if (Correct[i] == Vec[i]) {
            Count++;
        }
    }
    Answer = max(Answer, Count);

    for (int i = 0; i < N; i++) {
        if (Vec[i] > 0) {
            vector<int> Tmp;
            Tmp.resize(N);
            Tmp = Vec;
            for (int j = i; j < N; j++) {
                Tmp[j] = Tmp[j + 1];
            }
            Tmp[N - 1] = 0;
            DFS(Depth + 1, Tmp);

            Tmp = Vec;
            for (int j = (N - 1); j > i; j--) {
                Tmp[j] = Tmp[j - 1];
            }
            Tmp[i] = 0;
            DFS(Depth + 1, Tmp);
        }
    }
}

void settings() {
    DFS(0, MAP);
}

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

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

    return 0;
}