BOJ 17281 야구

작성일 | In |

Problem : 야구

유형 : 완전탐색, 구현

문제 해석

  • 주어진 야구 규칙에 맞춰서 게임을 진행한다
  • 각 선수 별로 이닝 마다 치는 타격이 정해져 있다.
  • 1번선수는 항상 4번 타석에 선다.
  • 최고 점수를 구하라.

문제 재해석

  • 전부 다 해보면 되는 완탐, 시뮬 문제이다.

해결 전략

  • 1번 선수를 제외하고 나머지 선수로 만들 수 있는 모든 조합을 만든다.
  • 그리고 시뮬레이션 하면서 모든 조합에 따른 결과를 다 뽑아본다.

설계, 구현

  • 1번 선수를 제외하고 permutation으로 모든 조합을 만들어본다.
  • 1번 선수는 4번 타석에 넣는다.
  • 게임을 진행하는데, 해당 이닝이 끝나도 순서는 계속 이어지게 한다.
    • 이 부분을 큐로 구현했었는데 시간이 상당히 오래 걸려서 재 설계 했다.
    • 어차피 선수는 9명으로 고정되어있으니 10번째 차례는 1번 선수로 돌아가게 했다.
  • 아웃이 아닌 경우에는, 0 ~ 3루에 선수가 있다면 전부 타격의 포인트 N 만큼 움직이게 했다.
  • 이동 하려는 것이 4루 이상이면 점수를 내게 했다.
  • 방금 친 타자도 N루로 움직이게 했다.

주의할 점

  • 이 야구는 50이닝까지 가능하다 처음에 9이닝인줄 알고 잘못 구현했었다.
  • 타석의 타자를 움직이지 않는 실수를 할뻔했다.

디버깅

  • 큐를 이용해서 처음에 설계한 방법은, 실행 시간이 오래걸렸다.
  • 삽입 삭제 과정이 잦아 시간을 초과 시키는 원인이 되는 것 같아서 재설계했다.
  • 큐를 이용한 것도, 밀어내기 방식으로 움직여야 되는 줄 알고 큐로 구현한 것인데 문제를 잘못 읽었었다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <bits/stdc++.h>
using namespace std;

bool spot[4];
int player[52][10]; //[이닝][선수번호]
int n ,answer;

int order[10];
vector<int> vec = { 2,3,4,5,6,7,8,9 };

int Hit_Run(int hit) {
    int get_score = 0;

    for (int i = 3; i >= 1; --i) {
        if (spot[i]){
            if (i + hit >= 4) get_score++;
            else spot[i + hit] = true;

            spot[i] = false;
        }
    }

    if (hit == 4) get_score++;
    else spot[hit] = true;

    return get_score;
}

int Game() {
    int score = 0;
    int cnt = 1;

    for (int inning = 1; inning <= n; ++inning) {
        int out = 0;
        memset(spot, false, sizeof(spot));

        while (1) {
            int cur_player = order[cnt];
            cnt = cnt % 9 + 1;

            int hit = player[inning][cur_player];

            if (hit == 0) {
                out++;
                if (out == 3) break;
                continue;
            }

            score += Hit_Run(hit);
        }
    }

    return score;
}

void Make_Order() {

    for (int i = 1; i <= 9; ++i) {
		if (i < 4) order[i] = vec[i - 1];
		else if (i == 4) order[i] = 1;
		else order[i] = vec[i - 2];
    }
}

void Solve() {
    
    do {
        Make_Order();
        answer = max(answer, Game());
    } while (next_permutation(vec.begin(), vec.end()));

    cout << answer << "\n";
}

void Input() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        for (int ii = 1; ii <= 9; ++ii) {
            cin >> player[i][ii];
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);
    //freopen("input.txt", "r", stdin);

    Input();
    Solve();

    return 0;
}

피드백

  • 배경 지식에 의존 하지 말고 문제에서 주어진 대로만 구현하자.