[백준 28286번] 재채점을 기다리는 중 (C++)

문제링크 : https://www.acmicpc.net/problem/28286

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

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, K;
vector<int> answer(21);
vector<int> OMR(21);
int maxV = 0;

void dfs(int depth, vector<int>v)
{
    int cnt = 0;
    for(int i=0; i<N; i++)
    {
        if(answer[i] == v[i]) cnt++; //정답수 카운트
    }
    maxV = max(maxV, cnt); //최대 정답수 저장
    if(depth == K) return; //밀고 당기는 횟수 체크

    for(int i=0; i<N; i++)
    {
        vector<int>tmp(21); //밀고 당겨진 값을 담을 배열
        tmp = v;
        rotate(tmp.begin()+i, tmp.begin()+i+1, tmp.end()); //한칸씩 왼쪽으로 이동
        tmp[N-1] = 0; //맨 뒤에 값 0으로
        dfs(depth+1, tmp);

        tmp = v;
        rotate(tmp.begin()+i, tmp.end()-1, tmp.end()); //한칸씩 오른쪽으로 이동
        tmp[i] = 0; //앞에 값을 0으로
        dfs(depth+1, tmp);
    }
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    cin >> N >> K;
    for(int i=0; i<N; i++)
    {
        cin >> answer[i];
    }

    for(int i=0; i<N; i++)
    {
        cin >> OMR[i];
    }

    dfs(0, OMR);
    cout << maxV;
    return 0;
}

OMR에 대해 확인하는 경우가 밀기와 당기기 2가지이다.

각각의 위치에 대해 전부 밀기와 당기기를 하여 모든 경우의 수를 체크하고 최대 정답수 일때를 저장해준다.

 

여기서 밀기와 당기기를 할때 rotate 함수를 사용하여 한칸씩 밀기 또는 당기기를 쉽게 할 수 있다.

그리고 밀기와 당기기 횟수가 K로 정해져 있기에 해당 횟수가 K가 되면 멈추도록 한다.