백준 17281 - ⚾(골드4)

문제

백준 17281 - ⚾
(https://www.acmicpc.net/problem/17281)

재밌는 야구 문제이다.

접근법

일단 1번 선수는 4번 타자로 고정이고, 나머지 선수들의 순서를 정해주어야 한다.
1번 선수를 제외한 나머지 선수들의 순서를 정해준다. (순열 알고리즘)

그다음 입력에서 받은 선수들의 행동들을 통해서 게임을 시뮬레이션한다.
각 이닝의 시작마다 베이스(루)와 아웃카운트는 모두 비운다.

그 후 각 선수들의 결과를 토대로 베이스의 상태, 아웃카운트, 점수를 관리한다. 3아웃이 되면 다음 이닝으로 넘어간다.

선수들의 순서에 따라 얻는 점수가 달라지는데, 그 중 최댓값을 출력한다.

야구의 룰을 알아서 그런지 시뮬레이션을 재밌게 구현했다.

구현

#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;
int n;
int man[51][10];
vector<int> line;
int ans=-1;
int pos=0;
int visit[10]={0,};
int simulation(int n)
{
	int base[4];
	int score=0;
	for(int i=1;i<=n;i++)
	{
		
		int out=0;
		memset(base,0,sizeof(base));
		while(out<3)
		{
			if(man[i][line[pos]]==1)//안타
			{
				if(base[3]==1)
				{
					base[3]=0;
					score++;
				}
				if(base[2]==1)
				{
					base[2]=0;
					base[3]=1;
				}
				if(base[1]==1)
				{
					base[1]=0;
					base[2]=1;
				}
				
				base[1]=1;
			}
			else if(man[i][line[pos]]==2)//2루타
			{
				if(base[3]==1)
				{
					base[3]=0;
					score++;
				}
				if(base[2]==1)
				{
					base[2]=0;
					score++;
				}
				if(base[1]==1)
				{
					base[1]=0;
					base[3]=1;
				}
				
				base[2]=1;
			}
			else if(man[i][line[pos]]==3)//3루타
			{
				if(base[3]==1)
				{
					base[3]=0;
					score++;
				}
				if(base[2]==1)
				{
					base[2]=0;
					score++;
				}
				if(base[1]==1)
				{
					base[1]=0;
					score++;
				}
				
				base[3]=1;
			}
			else if(man[i][line[pos]]==4)//홈런
			{
				if(base[3]==1)
				{
					base[3]=0;
					score++;
				}
				if(base[2]==1)
				{
					base[2]=0;
					score++;
				}
				if(base[1]==1)
				{
					base[1]=0;
					score++;
				}
				
				score++;
			}
			else//아웃
			{
				out++;
			}
			
			pos=(pos+1)%9;//마지막 타자 까지 치면 다시 첫번째 순서로
		}
	}
	
	return score;
}
void check(int depth,int end)
{
	if(depth==end)//1번 선수를 제외한 나머지 8명의 순서를 정하면
	{
		
		line.insert(line.begin()+3,1);//1번 선수를 4번 순서에 꽂아 넣는다.
		
		
		pos=0;
		ans=max(ans,simulation(n));
		line.erase(line.begin()+3);//4번 순서에 꽂았던 선수를 뺀다.
		

	}
	else//8명의 선수의 순서를 정하기 위한 순열 알고리즘
	{
		
		for(int i=2;i<=9;i++)
		{
			if(!visit[i])
			{
				visit[i]=1;
				line.push_back(i);
				check(depth+1,end);
				line.pop_back();
				visit[i]=0;
			}
		}
	}
}
int main()
{
	
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=9;j++)
		{
			scanf("%d",&man[i][j]);
		}
	}
	memset(visit,0,sizeof(visit));
	check(0,8);
	printf("%d",ans);
	return 0;
}