17281 ⚾

문제 링크

#include <bits/stdc++.h>

using namespace std;

vector<int> p = { 1, 2, 3, 4, 5, 6, 7, 8 };
vector<vector<int>> scbd;
int n, iidx;

int calc(int num, vector<int>& base) {
    if (!num)
        return -1;
    int score = 0;
    for (int i = 0; i < num; i++) {
        /*base.push_back(!i); // vector가 deque보다 훨씬 빠르다
        score += base.front();
        base.pop_front();*/
        score += base[2];
        base[2] = base[1];
        base[1] = base[0];
        base[0] = !i;
    }
    return score;
}

int run_simul(const vector<int>& lst) {
    int ret = 0;
    int    pidx = 0; // 선수 인덱스
    // 현 선수 리스트로 모든 이닝을 순회
    for (int inning = 0; inning < n; inning++) {
        int out = 0, t;
        vector<int> base(3, 0);
        while (out < 3) {
            //base[0] = base[1] = base[2] = 0;
            t = calc(scbd[inning][lst[pidx]], base);
            if (t == -1)
                out++;
            else
                ret += t;
            pidx = (pidx + 1) % 9;
        }

        //if (ret == 43)
            //cout << " ";
    }
    return ret;
}

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

    cin >> n;
    scbd.resize(n, vector<int>(9, 0));

    for (auto& a : scbd)
        for (auto& b : a)
            cin >> b;

    int ret = 0, inning = 0;
    time_t st, ed;
    st = clock();
    do {
        vector<int> lst;
        lst.insert(lst.end(), p.begin(), p.begin() + 3);
        lst.push_back(0);
        lst.insert(lst.end(), p.begin() + 3, p.end());

        ret = max(ret, run_simul(lst));
    } while (next_permutation(p.begin(), p.end()));
    ed = clock();
    cout << ret << "\n";
    cout << ed - st << "\n";
}

vector가 deque보다 훨씬 빠름!  위에서 부터  deque 이용, deque index활용, vector이용,

9
1 2 4 3 0 2 1 0 3
1 2 1 2 0 0 0 0 1
3 4 2 3 1 2 3 4 0
0 1 2 3 4 2 1 0 0
0 0 0 0 0 0 1 4 4
0 4 0 4 0 4 0 4 0
0 4 2 2 2 2 2 2 2
1 1 1 1 1 1 1 1 0
0 2 0 3 0 1 0 2 0
89
254

C:\Users\User\source\repos\profile01\Baekjoon\x64\Release\17281.exe(6076 프로세스)이(가) 0 코드로 인해 종료되었습니다.
이 창을 닫으려면 아무 키나 누르세요.

9
1 2 4 3 0 2 1 0 3
1 2 1 2 0 0 0 0 1
3 4 2 3 1 2 3 4 0
0 1 2 3 4 2 1 0 0
0 0 0 0 0 0 1 4 4
0 4 0 4 0 4 0 4 0
0 4 2 2 2 2 2 2 2
1 1 1 1 1 1 1 1 0
0 2 0 3 0 1 0 2 0
89
150

C:\Users\User\source\repos\profile01\Baekjoon\x64\Release\17281.exe(2944 프로세스)이(가) 0 코드로 인해 종료되었습니다.
이 창을 닫으려면 아무 키나 누르세요.

9
1 2 4 3 0 2 1 0 3
1 2 1 2 0 0 0 0 1
3 4 2 3 1 2 3 4 0
0 1 2 3 4 2 1 0 0
0 0 0 0 0 0 1 4 4
0 4 0 4 0 4 0 4 0
0 4 2 2 2 2 2 2 2
1 1 1 1 1 1 1 1 0
0 2 0 3 0 1 0 2 0
89
73

C:\Users\User\source\repos\profile01\Baekjoon\x64\Release\17281.exe(11560 프로세스)이(가) 0 코드로 인해 종료되었습니다.
이 창을 닫으려면 아무 키나 누르세요.

insert를 사용안하면 속도를 더 단축할 수 있다.

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int N; cin >> N;
    int score = 0;
    int player[50][9];
    int chance[4];
    for(int i = 0; i < N; i++)
        for(int j = 0; j < 9; j++) {
            cin >> player[i][j];
        }
    int curidx[8];
    for(int j = 0; j < 8; j++)
        curidx[j] = j+1;

        do {
            memset(chance, 0 ,sizeof(chance));
            int idx[9];
            int out = 0;
            int prevscore = 0;
            int inning = 0;

            for(int i = 0; i < 3; i++)
                idx[i] = curidx[i];
            for(int i = 3; i < 8; i++)
                idx[i+1] = curidx[i];
            idx[3] = 0;

            int start = 0;
            while(inning < N) {
                int p = player[inning][idx[start]];
                if(p != 0) {
                    for(int k = 3; k >= 1; k--) {
                        if(chance[k] == 1) {
                            if(k+p >= 4) prevscore++;
                            else chance[k+p] = 1;
                            chance[k] = 0;
                        }
                    }
                    if(p == 4) prevscore++;
                    else chance[p] = 1;

                }
                else out++;

                if(out==3) {
                    out = 0;
                    inning++;
                    memset(chance, 0 , sizeof(chance));
                }
                start = (start+1)%9;
            }
            score = max(score,prevscore);
        } while(next_permutation(curidx, curidx+8));
    cout<<score;
    return 0;
}