[백준][C++] 17281 야구

 

 

 

알고리즘 종류

    - 구현

    - 브루트포스

 

 

 

사고 과정

    1. 순열조합으로 타자의 순서 정하기

    2. 각 조합에 따라 점수 구하기

        조건 1. 3 아웃이면 이닝 종료

        조건 2. 타순은 한 이닝이 끝나면, 다음 이닝에서 계속 이어짐

        조건 3. 안타면 모든 선수 1칸 이동, 2루타면 모든 선수 2칸 이동, ...

    3.  각 조합의 모든 이닝이 끝나면 다른 조합의 결과와 점수 비교하여 최고 점수 저장

 

 

 

구현(C++)

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
int n;
int answer = 0;
// 각 이닝에서 타자의 결과
int mat[51][10];
int isSelected[10];
// 타순(타자가 치는 순서) 
vector<int> seq;
 
void get_score(){
    
    int game = 1;
    // 선수의 순서는 이닝 전체에 적용됨으로 여기에 선언 
    int turn = 1;
    int score = 0;
    // 필드 상태. 홈:0, 1루:1. 2루:2, 3루:3, 점수:4 
    int state[5];
    
    vector<int> seq2 = seq;
    // 1번 타자를 4번 순서에 넣기 
    seq2.insert(seq2.begin()+3, 1);
    
    while(true){
        // 이닝 횟수  
        if(game == n+1) break;
        
        int out = 0;
        // 이닝마다 필드 상태 초기화  
        memset(state, 0, sizeof(state));
        
        // 3아웃이면 이닝 종료 
        while(out != 3){
            
            // 순서에 해당하는 선수의 결과가 0이면(아웃)  
            if(mat[game][seq2[turn-1]] == 0){
                out++;
                turn++;
                if(turn == 10) turn = 1;
                continue;
            } else {
                // 아웃 아니면 필드에 나갈 준비  
                state[0] = 1;
            }
            
            // 필드에 나가게 되면, 선수들을 밀어야 한다.  
            for(int i=3; i>=0; i--){
                // 밀려났을 때, 홈으로 들어가면 점수 +1 
                if(i + mat[game][seq2[turn-1]] >= 4){
                    if(state[i]){
                        state[4]++;
                        state[i] = 0;
                    }
                }
                // 밀렸을 때, 홈에 들어가지 못하면, 위치 옮기기  
                else if(i + mat[game][seq2[turn-1]] < 4){
                    if(state[i]){
                        state[i + mat[game][seq2[turn-1]]] = 1;
                        state[i] = 0;
                    }
                }
            }
            
            // 선수가 쳤으니 다음 순서  
            turn++;
            if(turn == 10) turn = 1;
        }
        
        // 3 아웃으로 1회 이닝이 끝나면 점수 저장하기  
        score += state[4];
        game++;
    }
    
    // 모든 이닝이 끝나고 다른 순서 조합과 비교하기  
    answer = max(answer, score);
    
}
 
void combination(int cnt){
    if(cnt == 9){
        // 조합에 의한 순서로 점수 구해보기  
        get_score();
        return;
    }
 
    // 1번 타자 제외하고 순서 정하기     
    for(int i=2; i<=9; i++){
        if(isSelected[i]) continue;
        isSelected[i] = 1;
        seq.push_back(i);
        combination(cnt+1);
        seq.pop_back();
        isSelected[i] = 0;
    }
}
 
 
void solution(){
    // 순열조합으로 타순 결정하기  
    combination(1);
    cout << answer << endl;
}
 
 
int main(void){
    cin >> n;
    
    for(int i=1; i<=n; i++){
        for(int j=1; j<=9; j++){
            cin >> mat[i][j];
        }
    }
    solution();
}
 
 

 

 

 

시행착오

    - 각 이닝에서 선수의 순서가 바뀌는 줄 알고 걱정하느라 시간을 낭비했다. 안 바뀌는데...

    - 타자가 공을 치고 필드에 나갈 때 어떻게 선수들을 움직이고 점수를 옮길까 고민했다. 나눗셈으로 할까 queue를 쓸까 고민했다. 결국 배열을 각 필드를 나타내기로 했다. state[5]로 만들어서, [0]은 홈이고 [3]은 3루로 정했다. 그리고 [4]는 점수를 저장하기로 했다. 3루에서 홈으로 들어가면 1점이니 그것을 표현했다.

    - 그닥 어렵지 않았지만, 야구라는 소재를 사용해서 본인 혼자 어렵게 느꼈던 것 같다. 야구 경기를 본 경험도 없고 규칙도 거의 모르기 때문일 것이다.