백준 [17281] "야구"

야구 룰을 알고 있다면 문제 이해에는 큰 어려움이 없던 문제였다.

문제의 핵심 포인트는 개인적으로 2가지로 생각했는데

첫번째는 아웃 카운트를 통해 이닝을 종료 시키는것 그리고
두번째는 타순을 모두 섞어 진행 하는 것이다.

첫번째는 out_count라는 변수를 찾아 타순의 값이 0일 경우 out_count를 증가해 해결했지만 타순을 섞어 진행하는 것은 감을 찾지 못해 답안을 찾아보았다.

대부분의 답안에서는 algorithm STL의 next_permutation함수를 이용하여 타순의 모든 경우의 수를 알아보았다.

next_permutation은 bool type를 return하는데 만약 다음 순열이 존재할 경우 true를 리턴해 다음 검사를 진행하게 하였고 만약 false가 나온 경우는 더이상의 타순 경우의 수는 존재하지 않기 때문에 break을 통해 지금까지 나온 score 수 중에 max를 구해 return 하였다.

1. 주어진 배열에서 가능한 모든 순열 중에서 현재 순열의 다음 순열을 구합니다. 여기서 "다음"이란, 사전순으로 바로 다음에 위치하는 순열을 의미합니다.

2. 다음 순열이 존재하는 경우, 그 순열을 반환하고 true를 반환합니다.

3. 더 이상 다음 순열이 없을 경우(즉, 현재 순열이 내림차순으로 정렬된 마지막 순열이라면), 순열을 첫 번째 순열로 되돌리고 false를 반환합니다.

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <deque>

using namespace std;

int s[50][9];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n; cin >> n;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < 9; j++)
            cin >> s[i][j]; // 각 선수가 이닝에서 얻는 결과를 입력 받음.

    int np[8] = { 1, 2, 3, 4, 5, 6, 7, 8 };

    int ans = 0;
    while(next_permutation(np,np+8)){

        deque<int> h;
        for (int i = 0; i < 3; i++) h.push_back(np[i]);   // 타자 순서
        h.push_back(0); // 4번 타자에 1번 선수를 넣음
        for (int i = 3; i < 8; i++) h.push_back(np[i]);

        int ining = 0, score = 0;
        while (ining < n) {   // 게임 시작
            int out = 0;    // 현재 이닝에서의 out 횟수
            queue<int> base; for (int i = 0; i < 3; i++) base.push(0);   // base를 모두 0으로 채움

            while (out < 3) { // 3아웃이 발생할 때까지 이닝 진행
                int cur = h.front(); // 현재 타자
                h.pop_front(); h.push_back(cur);   // 현재 타자를 마지막 타자로 다시 넣음
                if (s[ining][cur] == 0) out++;   // 아웃인 경우
                else {   // 아웃이 아닌 경우
                    if (base.front() == 1) score++;  // 3루수 홈으로 진루
                    base.push(1); base.pop();   // 1루로 진루
                    for (int i = 0; i < s[ining][cur] - 1; i++) { // 나머지 진루
                        if (base.front() == 1) score++;
                        base.pop(); base.push(0);
                    }
                }
            }
            ining++;    // 이닝 증가
        }   // 게임 종료
        ans = max(ans, score);
    } 
    cout << ans;
}