[백준] 17281번: ⚾

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

17281번: ⚾

 

나머지 예제 생략

 

문제 이름이 ⚾ 라서 검색하기도 힘든 문제;;;

암튼

문제 이해

문제의 요점은, 10명의 선수의 순서를 정하고 (DFS)

이닝(행) 별 선수 성적(열)에 맞춰서 그 순서에서 얻을 수 있는 점수를 계산해서,

그 중 최대값을 찾아라

이다

 

DFS는 그리 어렵지 않게 짤 수 있고,

그 타순으로 시뮬레이션을 돌려보는게 좀 복잡한 부분이다.

 

나는 base라는 배열을 만들어서 각 베이스 별로 선수 유무를 기록해뒀고,

이닝을 돌려가면서 각 이닝 별 아웃 카운트가 3보다 작을 때까지 base에 이미 오른 애들은 진루하고,

만약에 홈으로 들어온 애가 있으면 포인트를 증가시키는 식으로 구현했다.

 

내가 좀 헛짓거리 한 부분은, base를 이닝마다 초기화해줘야 한다는 것,

0루, 즉 홈에는 항상 선수가 있다는 것 (타자) 등이다.

 

이 문제는 그냥 각종 배열 - 이닝 별 선수 성적 배열(arr), 선수 순서를 정한 배열(seq) 를 안헷갈리면 되는 것 같다!

 

작성 코드

#include <iostream>
#include <cstring>
using namespace std;
#define MAXN 50

int N; // 이닝 수
int arr[MAXN + 5][9 + 2]; // 각 이닝별 1~9번 타자 결과
int seq[9 + 2]; // 순서
int max_pnt; // 최고 점수

void Get_Input(void) {
    cin >> N;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= 9; j++) {
            cin >> arr[i][j];
        }
    }
}

int Try_Simulation(void) {
    int cur = 1;
    int base[4] = { 0, };
    int pnt = 0;
    for (int n = 1; n <= N; n++) {
        // n번 이닝에서부터 시작
        int out_cnt = 0;
        memset(base, 0, sizeof(base));
        while (out_cnt < 3) {
            // n번 이닝의 cur번 타자의 결과는 arr[n][seq[cur]]에 있음
            base[0] = 1;
            if (arr[n][seq[cur]] == 0) out_cnt++;
            else {
                // arr[n][sec[cur]] 만큼 진루
                int go = arr[n][seq[cur]];
                for (int i = 3; i >= 0; i--) {
                    if (base[i] == 1) {
                        if (i + go >= 4) pnt++;
                        else base[i + go] = 1;
                        base[i] = 0;
                    }
                }
            }
            cur = (cur + 1 > 9) ? 1 : cur + 1;
        }
    }
    return pnt;
}

void DFS(int pno) {
    // 종료
    if (pno == 10) {
        // 다 골랐음 -> 이 순서에서 시뮬 돌려서 몇 점 얻는지 확인
        int tmp = Try_Simulation();
        if (tmp > max_pnt) max_pnt = tmp;
        return;
    }
    // 재귀
    for (int i = 1; i <= 9; i++) {
        if (seq[i] != 0) continue;
        seq[i] = pno;
        DFS(pno + 1);
        seq[i] = 0;
    }
}

int main(void) {
    freopen("in.txt", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    Get_Input();
    // 1번 타자는 무조건 4번
    seq[4] = 1;
    DFS(2); // 2번 타자부터 몇 번 타석에 설 지 정해라
    cout << max_pnt;
    return 0;
}