BOJ 17281 - ⚾ (C++)

https://www.acmicpc.net/problem/17281

문제를 푼 날짜: 24. 05. 29.

#implementation #bruteforcing

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <array>
using namespace std;

//총 이닝 수
int N;

// 각 이닝에 #번 선수의 결과 (편의상 0회부터, 0번 선수부터 시작으로 생각)
int player_result[51][10];

// 타순 전달받아 점수 return하는 함수
int scorePredict(vector<int>& lineup);

//안타, 2루타, 3루타, 홈런
pair<array<int, 3>, int> singleHit(array<int, 3> base_situation, int score);
pair<array<int, 3>, int> doubleHit(array<int, 3> base_situation, int score);
pair<array<int, 3>, int> tripleHit(array<int, 3> base_situation, int score);
pair<array<int, 3>, int> homerunHit(array<int, 3> base_situation, int score);

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    int score, max_score = -1;
    vector<int> lineup = {0, 1, 2, 3, 4, 5, 6, 7, 8}; // 0번 선수 ~ 8번 선수

    cin >> N;

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

   
    do{
        // 4번타자는 무조건 0번 선수여야만 함
        if(lineup[3] != 0) continue;
        
        score = scorePredict(lineup);
        if(score > max_score) max_score = score;
    } while(next_permutation(lineup.begin(), lineup.end()));

    cout << max_score;

    return 0;
}

int scorePredict(vector<int>& lineup){
    int score = 0;
    int out_count = 0;
    array<int, 3> base_situation = {0, 0, 0}; // 1루, 2루, 3루
    int inning = 0; // 현재 몇 회인지지, 편의상 시작을 0회로
    pair<array<int, 3>, int> tmpresult; // basesituation과 score 받는 tmp variable

    while(1){
        for(int hitter : lineup){
            switch(player_result[inning][hitter]){
                //0-아웃, 1-안타, ..., 4-홈런
                case 0:
                    out_count++;
                    if(out_count == 3){
                        base_situation[0] = 0;
                        base_situation[1] = 0;
                        base_situation[2] = 0;
                        
                        inning += 1;
                        out_count = 0;

                        //이닝을 더했을 때 N이면 경기 종료
                        if(inning == N) return score;

                    }
                    break;
                case 1:
                    tmpresult = singleHit(base_situation, score);
                    base_situation = tmpresult.first;
                    score = tmpresult.second;
                    break;
                case 2:
                    tmpresult = doubleHit(base_situation, score);
                    base_situation = tmpresult.first;
                    score = tmpresult.second;
                    break;
                case 3:
                    tmpresult = tripleHit(base_situation, score);
                    base_situation = tmpresult.first;
                    score = tmpresult.second;
                    break;
                case 4:
                    tmpresult = homerunHit(base_situation, score);
                    base_situation = tmpresult.first;
                    score = tmpresult.second;
                    break;
                default:
                    cout << "BIG PROBLEM!" << '\n';
                    break;
            }
        }
    }
}
   
pair<array<int, 3>, int> singleHit(array<int, 3> base_situation, int score){
    if(base_situation[2] == 1){
        base_situation[2] = 0;
        score++;
    }
    if(base_situation[1] == 1){
        base_situation[1] = 0;
        base_situation[2] = 1;
    }
    if(base_situation[0] == 1){
        base_situation[1] = 1;
    }

    base_situation[0] = 1;

    return make_pair(base_situation, score);
}

pair<array<int, 3>, int> doubleHit(array<int, 3> base_situation, int score){
    if(base_situation[2] == 1){
        base_situation[2] = 0;
        score++;
    }
    if(base_situation[1] == 1){
        score++;
    }
    if(base_situation[0] == 1){
        base_situation[0] = 0;
        base_situation[2] = 1;
    }

    base_situation[1] = 1;

    return make_pair(base_situation, score);
}

pair<array<int, 3>, int> tripleHit(array<int, 3> base_situation, int score){
    if(base_situation[2] == 1){
        score++;
    }
    if(base_situation[1] == 1){
        base_situation[1] = 0;
        score++;
    }
    if(base_situation[0] == 1){
        base_situation[0] = 0;
        score++;
    }

    base_situation[2] = 1;

    return make_pair(base_situation, score);
}

pair<array<int, 3>, int> homerunHit(array<int, 3> base_situation, int score){
    for(int i = 0; i < 3; i++){
        if(base_situation[i] == 1){
            base_situation[i] = 0;
            score++;
        }
    }

    score++;

    return make_pair(base_situation, score);
}

아이디어

최대 계산 횟수: 50 이닝 * (9-1)!
(1번 선수를 4번타자로 고정하고 나머지 선수에 대한 라인업의 경우의 수)
=> BruteForce!

• 캡슐화를 통해 코드의 가독성을 높이는 것을 목표로 했음.

• main 함수에서 타순을 만들면, 타순을 입력받아 그 타순이 내는 점수를 return하는 함수(scorePredict)를 만드는 틀을 생각함. 모든 타순에 대해 실행한 후, 최대 스코어를 답으로 출력.

• scorePredict 함수에서는 안타, 2루타, 3루타, 홈런 및 아웃 상황 시 아웃카운트, 스코어, 누상상황을 업데이트 해야하기 때문에, 각각의 상황이 발생했을 때 변수들을 업데이트하는 보조함수를 작성함.

얻어갈 부분

1. 문제를 처음 봤을 때는 막연하게 “이걸 어떻게 구하지?”라는 생각이 있었는데,
   naive한 방법 (시간초과를 걱정하지 않고)부터 시도하자는 마인드로 접근하니 BruteForce 문제였다.

2. 처음 풀었을 때 기본적으로 주어진 test case에서 틀렸는데, 1번 선수를 4번타자로 고정한다는 조건을 놓쳐서 그런 것이었다.
   추가적으로, 3아웃 시 누상상황이 초기화된다는 점도 고려하지 않았었다.
   문제에서 놓치는 조건이 없도록 주의하는 습관을 들이자.

3. singleHit, doubleHit… 의 함수를 만들 때
   여러 개의 인자를 return 해야 하기 때문에 ‘pair’과 ‘array’를 이용했는데,
   reference를 이용하여 인자를 받으면 여러 개의 값을 return할 걱정을 하지 않아도 된다!