[ 백준 ] 17281 / ⚾

金弘均·2021년 9월 14일
0

Baekjoon Online Judge

목록 보기
9/228
post-thumbnail
post-custom-banner

# Appreciation

/*
 * Problem :: 17281 / ⚾
 *
 * Kind :: Brute Force + Simulation
 *
 * Insight
 * - 야구 시뮬레이션이다
 *   타자의 순서를 정해야 하는데
 *   최대 점수를 얻을 수 있게끔 타순을 정하는 알고리즘을 도저히 찾을 수 없을 것 같다
 *   1번 선수는 4번 타자로 고정이니 8! 정도만 살펴보면 된다
 *   브루트 포스로 풀자!
 *   + 조금 복잡해보이지만
 *     타순이 정해졌을 때 해당 이닝의 각 선수별 결과를 얻고
 *     이를 해당 이닝의 출루 상황에 반영시키면 된다
 *
 * Point
 * - 출루에 따른 점수를 얻는 방식은 Vector, Array 등 다양할 것 같다
 *   + 먼저 생각났던 Boolean Array 로 해결했다
 *     # 이전에는 Deque 으로 해결했더라
 *       -> 이외에도 다양한 방법이 있을 듯 싶다
 *
 * - Zero-based Numbering
 *   문제와 다르게 편의상 0 부터 시작하는 인덱스 넘버링을 사용했다
 *   + 1번 타자 => 0번 인덱스
 *     1번 이닝 => 0번 이닝
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

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

using namespace std;

#define endl '\n'

// Set up : Global Variables
/* None */

// Set up : Functions Declaration
/* None */


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    int N; cin >> N;
    int A[N][9];
    for (int i=0; i<N; i++)
        for (int j=0; j<9; j++)
            cin >> A[i][j];

    // Process
    vector<int> O = {1, 2, 3, 4, 5, 6, 7, 8}; /* 타순 초기화 */

    int ans = -1; /* 팀이 얻을 수 있는 최대 점수 */
    do {
        int tmp = 0; /* 현재 타순으로 얻을 수 있는 점수 */
        int idx = 0; /* 현재 타석 인덱스 */
        for (int i=0; i<N; i++) {
            int out = 0; /* 현재 이닝 아웃 카운트 */
            bool base[3+1]; /* 현재 출루 상황 */
            memset(base, false, sizeof(base)); /* 출루 상황 초기화 */
            vector<int> R(8); /* R[i] = 현재 이닝에서 i번 선수의 결과 */
            for (int j=0; j<8; j++) {
                R[j] = A[i][O[j]];
            } R.insert(R.begin()+3, A[i][0]); /* 1번 선수는 4번 타자 */

            while (out < 3) {
                int r = R[idx]; /* 현재 타석의 결과 */
                idx = (idx+1) % 9; /* 다음 타석 인덱스 */
                if (r == 0) { /* 결과가 아웃이면 */
                    out++;
                } else { /* 결과가 아웃이 아니라면 */
                    for (int j=3; j>=1; j--) { /* 3루부터 1루까지 주자 진루 */
                        if (base[j]) { /* 주자가 있다면 */
                            if (j+r >= 4) /* 홈에 들어왔다면 */
                                tmp++; /* 점수 증가 */
                            else /* 홈에 들어오지 못했다면 */
                                base[j+r] = true; /* 주자가 진루 */
                            base[j] = false; /* 주자가 출루해 현재 루엔 주자가 없음 */
                        }
                    }
                    if (r >= 4) /* 홈런이라면 */
                        tmp++; /* 점수 증가 */
                    else /* 홈에 들어오지 못했다면 */
                        base[r] = true; /* 주자가 진루 */
                }
            }
        }
        ans = max(ans, tmp);
    } while (next_permutation(O.begin(), O.end())); /* 다음 타순으로 */

    // Control : Output
    cout << ans << endl;
}

// Helper Functions
/* None */
profile
이런 미친 게임을 봤나! - 옥냥이
post-custom-banner

0개의 댓글