[백준 17281] ⚾

[백준 17281] ⚾

문제 링크

using namespace std;
int N, max_score;
int players[51][10];
vector<int> candidates;
int visit[9];
int field[4];
void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < 9; j++) {
            cin >> players[i][j];
        }
    }
}
void move(int cmp, int &score) {

    for(int i=3; i>=1; i--) {
        if(field[i]) {
            if(i + cmp >= 4) { // home in
                score++;
            } else {
                field[i + cmp] = 1;
            }
            field[i] = 0;
        }
    }

    if(cmp == 4) {
        score++;
    } else {
        field[cmp] = 1;
    }
    
}
void play() {

    int out = 0;
    int idx = 0;
    int score = 0;
    
    for(int inning = 0; inning < N; inning++) {
        out = 0;
        memset(field, 0, sizeof(field));
        while (true){
            if(idx == 9) idx = 0;
            int cmp = players[inning][candidates[idx]];

            if(cmp == 0) {
                out++;
                if(out == 3) { idx++; break; }
            } else {
                // move
                move(cmp, score);
            }
            idx++;
        }
    }
    max_score = max(max_score, score);   

}

void dfs() {
    if (candidates.size() == 8) {
        candidates.insert(candidates.begin() + 3, 0);
        play();
        candidates.erase(candidates.begin() + 3);
        return;
    }

    for (int i = 1; i < 9; i++) {
        if (!visit[i]) {
            visit[i] = 1;
            candidates.push_back(i);
            dfs();
            candidates.pop_back();
            visit[i] = 0;
        }
    }
}
void solve() {
    dfs();
    cout << max_score << endl;
}
int main() {
    input();
    solve();
    return 0;
}

• 조합(dfs) + 시뮬레이션 문제
• 0번째를 제외하고 1~8까지의 경우의 수를 모두 구한다. -> 선수들의 순서의 모든 경우의 수가 된다.
• 조합이 완성 될 때마다 4번째에 0번을 넣어 주고 시뮬레이션을 한다.
• 선수의 점수에 따라 주자들을 움직여야 하는데, 이 때 1부터가 아닌 3부터 진행 해야 덮어씌워지지 않는다.
• 모든 이닝을 돈 후 최대 값을 갱신 해 주면 된다.