[C++] 백준 17281 - 야구(⚾)

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

17281번: ⚾

<풀이>

1. 이닝 별 선수 타격을 입력받는다.

2. 1번 타자를 4번으로 고정했을 때, 타순을 잘 정해서 팀이 얻을 수 있는 최대 점수를 출력한다.

 

<해법>

1. 알고리즘 선택하기

=> 1번 타자를 4번으로 고정하고, 모든 경우의 타선을 다 해보아야합니다. 따라서, 저는 브루트포스를 선택하였습니다.

 

2. 시뮬레이션 구현하기

=> 타순이 정해졌으면, 시뮬레이션을 진행해야합니다. 시뮬레이션의 핵심은 문제의 조건에 맞는 정확한 구현입니다. 저는 시뮬레이션 구현에서 타선을 Queue로 구현하였습니다.

 

3. 구현 전 총정리

=> 아래는 저가 구현 전에 정리한 생각입니다.

(1) 브루트포스 중 DFS를 선택하고, 재귀함수로 모든 경우의 타선을 만들어본다.

(2) 타선이 완성됐으면, 시뮬레이션을 진행한다.(타선은 큐로 구현한다)

(3) 얻을 수 있는 최대 점수를 return한다.

자세한 구현은 아래 코드를 참조해주세요.

 

#include <iostream>
#include <string.h>
#include <algorithm>
#include <queue>
 
using namespace std;
 
int N;
int record[50][9];
int order[9];
bool visited[9];
int answer;
 
int getPoint(int hit, bool base[]) {
    int output = 0;
 
    base[0] = true;
    for (int i = 3; i >= 0; i--) {
        if (base[i]) { //주자가 있을 경우
            if (i + hit > 3) {  //홈인
                base[i] = false;
                output++;
            }
            else { //진루
                base[i] = false;
                base[i + hit] = true;
            }
        }
    }
    return output;
}
 
int simulation() {
    int output = 0;    
    int inning = 0;
    queue<int> q; //타선을 큐로 구현
    for (int i = 0; i < 9; i++) {
        q.push(order[i]);
    }
    
    while (inning < N) {
        bool base[4];
        memset(base, false, sizeof(base));
        int out = 0;
 
        while (out != 3) {
            int hitter = q.front();
            q.pop();
            
            int hit = record[inning][hitter];
            if (hit == 0) out++;
            else output += getPoint(hit, base);
            
            q.push(hitter);
        }
        inning++;
    }
 
    return output;
}
 
int ordering(int idx) {
    if (idx == 9) {
        return simulation();
    }
 
    int ret = 0;
    if (idx == 3) ret = ordering(idx + 1);
    else {
        for (int i = 0; i < 9; i++) {
            if (!visited[i]) {
                order[idx] = i;
                visited[i] = true;
                ret = max(ret, ordering(idx + 1));
                visited[i] = false;
            }
        }
    }
    return ret;
}
 
void solution() {
    visited[0] = true;
    order[3] = 0;
    answer = ordering(0);
}
 
int main() {
    //초기화
    N = 0;
    memset(record, 0, sizeof(record));
    memset(order, 0, sizeof(order));
    memset(visited, false, sizeof(visited));
    answer = 0;
 
    //입력
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < 9; j++) {
            cin >> record[i][j];
        }
    }
 
    //해법
    solution();
 
    //출력
    cout << answer << "\n";
 
    //종료
    return 0;
}

 

DFS와 시뮬레이션에 대해 알아볼 수 있는 문제였습니다.