[백준] 17281 ⚾ C++

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

17281번: ⚾

브루트포스 문제이고 시뮬레이션 방식으로 풀었다.

알고리즘은 다음과 같다.

1. 입력

vector에 array<int, 9>를 추가하는 방식으로 이닝별 선수들의 행동을 저장했다. 

2. 브루트포스
2-1. 1~9까지 순열 구하기(permutation)
2-2. 구한 순열로 시뮬레이션해서 점수 구하기
2-3. 최대 점수 갱신

1부터 9까지 숫자를 가지고 있는 배열(players_order)을 선언하고 algorithm 헤더에 있는 next_permutation으로 순열을 찾았다. 모든 순열을 순회하지만 네번째 자리는 항상 1인 값만 확인했다.

이렇게 찾은 순서로 시뮬레이션을 돌린다. 시뮬레이션은 아웃인지 아닌지 체크하는 함수를 만들고 아웃이 아니면 점수와 base를 갱신하고 아웃이면 넘어갔다. 총 세번의 아웃이면 그다음 이닝으로 넘어가면서 진행했다.

해당 순열의 시뮬레이션을 모두 돌린 이후엔 최대 점수를 갱신하고 다음 순열로 넘어간다.

3. 최대 점수 출력

모든 순열을 배회하고 나면 가장 큰 점수를 찾게 되므로 이 값을 출력한다.

#include <iostream>
#include <array>
#include <vector>
#include <algorithm> // next_permutation
using namespace std;
#define NUM_PLAYERS 9

bool play(int cur_player_play, int &score, array<int, 3> &bases)
{
  switch (cur_player_play)
  {
  case 0:
    return true;
  case 1:
    score += bases[2];
    bases[2] = bases[1];    bases[1] = bases[0];    bases[0] = 1;
    break;
  case 2:
    score += bases[1] + bases[2];
    bases[2] = bases[0];    bases[1] = 1;    bases[0] = 0;
    break;
  case 3:
    score += bases[0] + bases[1] + bases[2];
    bases[2] = 1;    bases[1] = 0;    bases[0] = 0;
    break;
  case 4:
    score += bases[0] + bases[1] + bases[2] + 1;
    bases[2] = 0;    bases[1] = 0;    bases[0] = 0;
    break;
  default:
    break;
  }

  return false;
}

int main()
{
  // 0 initial setting
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  // 1 input
  int N;
  cin >> N;
  vector<array<int, 9>> innings;
  for (int i = 0; i < N; i++)
  {
    array<int, 9> inning;
    for (int j = 0; j < 9; j++)
    {
      cin >> inning[j];
    }
    innings.push_back(inning);
  }
  // 2 bruteforce
  int max_score = 0;
  // 2-1 make permutations
  array<int, 9> players_order = {1, 2, 3, 4, 5, 6, 7, 8, 9};
  int break_cnt = 0;
  do
  {
    if (players_order[3] != 1)
      continue;

    int player_idx = 0;
    int score = 0;
    for (int i = 0; i < N; ++i) // inning start, inning = innings[i]
    {
      int out = 0;
      array<int, 3> bases = {0, 0, 0};
      while (out < 3)
      {
        int cur_player = players_order[player_idx] - 1;
        if (play(innings[i][cur_player], score, bases))
        {
          out++;
        }
        player_idx = (player_idx + 1) % 9;
      }
    }
    if (max_score < score)
    {
      max_score = score;
    }

  } while (next_permutation(players_order.begin(), players_order.end()));

  // 3 output
  cout << max_score << '\n';

  return 0;
}

파이썬으로 풀었는데 시간초과가 걸려 C++로 바꿔서 풀었다.

next_permutation이라는 것을 처음사용해봤는데 유용한듯 하다. algorithms 헤더에 있는 다른 함수들도 사용해봐야겠다