[백준 17281: 야구] (C++)

삼성 A형 기출 문제

https://www.acmicpc.net/workbook/view/2771

ㄴ야구⚾

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

 

 

 

l 문제

 

1. 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임 한 야구팀의 감독 아인타는 가장 많은 득점을 찾는 타순을 찾아서 그 때의 득점을 구하려고 한다.

2. 선수 1번 부터 9번까지의 선수가 있다.

3. 타자 실제로 타석에 올라가서 공을 치는 선수이다. 어떤 선수가 몇 번째 타자인지 정하는 것을 타순을 정한다고 한다. 타자가 공을 쳐서 얻을 수 있는 결과는 안타, 2루타, 3루타, 홈런, 아웃 중 하나이다. 1: 안타: 타자와 모든 주자가 한 루씩 진루한다. 2: 2루타: 타자와 모든 주자가 두 루씩 진루한다. 3: 3루타: 타자와 모든 주자가 세 루씩 진루한다. 4: 홈런: 타자와 모든 주자가 홈까지 진루한다. 0: 아웃: 모든 주자는 진루하지 못하고, 공격 팀에 아웃이 하나 증가한다.

3. 타순 타순은 경기중에 바꿀 수 없으므로 경기 시작 전에 선수들의 타순을 정해야 한다. ( 1번 선수는 4번 타자로 고정이다. ) 1번 타자 부터 9번 타자까지 순서대로 타석에 서며 9번 타자가 치고나면 다시 1번 타자가 타석에 선다. 타순은 이닝이 넘어가도 유지된다.

4. 이닝 한 이닝에 3아웃이 발생하면 다음 이닝으로 넘어간다.

 

 

l 입력

 

첫째 줄에 이닝 수 N(2 ≤ N ≤ 50)이 주어진다.

둘째 줄부터 N개의 줄에는 각 선수가 각 이닝에서 얻는 결과가 1번 이닝부터 N번 이닝까지 순서대로 주어진다. 이닝에서 얻는 결과는 9개의 정수가 공백으로 구분되어져 있다. 각 결과가 의미하는 정수는 다음과 같다. 안타: 1 2루타: 2 3루타: 3 홈런: 4 아웃: 0 각 이닝에는 아웃을 기록하는 타자가 적어도 한 명 존재한다.

 

 

l 출력

 

아인타팀이 얻을 수 있는 최대 점수를 출력한다.

 

l 풀이

 

선수들의 모든 순서를 조합하고 경기를 시작한다.

플레이 함수 {    for ( 모든 이닝 )        while ( ! 3아웃 )            선수들 차례로 이동 } 조합 함수 ( 재귀 ) {    if ( 8명의 선수를 다 뽑은 경우 )           4번 타자를 1번 선수로        return;    for( 2 ~ 9번 선수 )       if ( 선택 안된 선수 라면 )          1) 선택한다.          2) 선택 안한다. }

1번 선수 처리

나머지 선수들을 조합하여 8명이 완성되면 1번 선수를 4번 타자에 넣는다.

경기 주의 점

1. 이닝이 넘어가도 순서를 유지 2. 아웃 되었다고 해서 경기에서 완전히 빠지는 것이 아님 1번 ~ 9번 타자가 모두 공을 치고 다시 1번으로 돌아왔을 때 3. 몇 번 타자가 몇 루에 있는지 알 필요 없음 선수가 9명이나 되어서 반드시 자기 차례가 오기전에 3 아웃으로 다음 이닝 넘어가거나 다음 타자들로 인해 홈으로 들어온다.

 

 

l  코드

 

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int PLAYER_N = 9;
const int MAX_INNING = 50;

int N, ans;
int hit_type[MAX_INNING][PLAYER_N];
bool is_selected[PLAYER_N], is_ground_on[3];
vector<int> player_seq;

void move(int n, int &score)
{
	for (int i = 2; i >= 0; --i)
	{
		if (is_ground_on[i])
		{
			if (i + n >= 3) ++score;
			else is_ground_on[i + n] = true;
			is_ground_on[i] = false;
		}
	}
	if (n == 4) ++score;
	else is_ground_on[n - 1] = true;
}

void play()
{
	int inning, out_cnt, idx = 0, score = 0;
	for (inning = 0; inning < N; ++inning)
	{
		// 2. 이닝 시작 - 아웃, 주자 초기화
		out_cnt = 0;
		memset(is_ground_on, false, sizeof(is_ground_on));

		while (true)
		{
			if (idx >= PLAYER_N) idx = 0;

			// 3. 아웃되는 경우
			if (hit_type[inning][player_seq[idx]] == 0)
			{
				if (++out_cnt == 3)
				{
					++idx;
					break;
				}
			}
			else move(hit_type[inning][player_seq[idx]], score);
			++idx;
		}
	}
	ans = max(ans, score);
}

// 1. 선수들의 모든 순서 조합
void select()
{
	if (player_seq.size() == PLAYER_N - 1)
	{
		// 4번 타자는 반드시 1번 선수
		player_seq.insert(player_seq.begin() + 3, 0);
		play();
		player_seq.erase(player_seq.begin() + 3);
		return;
	}
	for (int i = 1; i < PLAYER_N; ++i)
	{
		if (!is_selected[i])
		{
			is_selected[i] = true;
			player_seq.push_back(i);
			select();
			player_seq.pop_back();
			is_selected[i] = false;
		}
	}
}
int main()
{
	// freopen("input.txt", "r", stdin);
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> N;
	register int i, j;
	for (i = 0; i < N; ++i)
		for (j = 0; j < PLAYER_N; ++j)
			cin >> hit_type[i][j];

	select();
	cout << ans;
	return 0;
}