[백준 17281] 야구

www.acmicpc.net/problem/17281

17281번: ⚾

야구 게임 구현이다.

 

1. dfs를 이용해서 타자 순서를 정하고

2. 정해진 순서대로 게임을 진행해서 점수를 계산한다.

 

1번 타자는 4번 순서로 고정이고 나머지 타자들 순서만 배치한다.

 

게임 진행 시엔 공을 친 결과에 따라 ground 배열값과 결과 값이 변한다.

0이면 out수만 증가

1이면 3루에 있던 사람 수 만큼 점수 증가, 나머지 루에서 한칸씩 이동

2와 3도 마찬가지이고 4의 경우 모든 루에 있던 사람들이 들어오고 ground 배열을 0으로 초기화한다.

 

처음 코드 짤 때 실수했던 점

out에 조건을 걸 때 out이 3의 배수일때마다 ining을 증가시켰다. 하지만 이러면 안된다...왜내면 매번 out이 업데이트되는게 아니기 때문이다. 연속으로 out이 나오지 않는 이상 1번순서도 3, 2번 순서도 3...

따라서 이닝이 증가할 때 out을 0으로 초기화해줘야한다.

 

아니면 이닝별로 for문을 돌리는 방법도 있다.

#include <stdio.h>

using namespace std;

int n;

int ball[50][10];

bool visited[9];
int order[9];
int ground[4];

int result = -1;

void game()
{
  int out = 0, ining = 0, idx = 0;
  int sum = 0;
  int cnt = 0;
  for (int i = 1; i < 4; i++)
  {
    ground[i] = 0;
  }

  while (1)
  {
    int cur = ball[ining][order[idx]];
    cnt++;
    if (cur == 0)
    {
      out++;
    }
    else if (cur == 1)
    {
      sum += ground[3];
      ground[3] = ground[2];
      ground[2] = ground[1];
      ground[1] = 1;
    }
    else if (cur == 2)
    {
      sum += (ground[2] + ground[3]);
      ground[3] = ground[1];
      ground[2] = 1;
      ground[1] = 0;
    }
    else if (cur == 3)
    {
      sum += (ground[1] + ground[2] + ground[3]);
      ground[3] = 1;
      ground[2] = 0, ground[1] = 0;
    }
    else
    {
      sum += (ground[1] + ground[2] + ground[3] + 1);

      for (int i = 1; i < 4; i++)
      {
        ground[i] = 0;
      }
    }

    if (out == 3)
    {

      ining++;

      if (ining == n)
      {
        break;
      }
      out = 0;
      for (int i = 1; i < 4; i++)
      {
        ground[i] = 0;
      }
    }

    idx = (idx + 1) % 9;
  }

  result = result < sum ? sum : result;
}

void DFS(int cnt)
{
  if (cnt == 9)
  {
    game();
    return;
  }

  for (int i = 1; i < 9; i++)
  {
    if (visited[i])
      continue;

    visited[i] = true;
    if (cnt == 3)
    {
      cnt++;
    }
    order[cnt] = i;
    DFS(cnt + 1);
    visited[i] = false;
  }
}

int main(void)
{
  scanf("%d", &n);
  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < 9; j++)
    {
      scanf("%d", &ball[i][j]);
    }
  }

  order[3] = 0;

  DFS(0);

  printf("%d\n", result);
  return 0;
}