BOJ 17281 : ⚾ (A형 상시)

 

A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기)

 

삼성 A형 전체 링크

www.acmicpc.net/workbook/view/2771 (상시 A형 문제집)

 

www.acmicpc.net/problem/17281

 

 

9명의 타자가 있고 1번 타자는 4번에 고정이므로, 8! = 40320번의 경우의 수에 대해 시뮬레이션을 하면 된다.

9명 타자를 줄 세우는 방법은 N과 M (1) - 순열의 방법을 이용한다.

 

input에서는 간단히 player의 결과를 저장한다.

void input()
{
	scanf("%d", &N);

	for (int i = 1; i <= N; i++)
		for (int k = 1; k <= 9; k++)
			scanf("%d", &player[i][k]);
}

 

먼저 1번 타자를 4번에 고정하면 경우의 수를 만드는데 처리해야할 코드가 추가되므로,

1번 타자는 1번에 고정하고 2 ~ 9번 타자에 대한 경우의 수를 만든다.

int main(void)
{
    input();

    list[1] = 1; /* 1번 타자는 1번에 고정 */
    DFS(2); /* 2번 부터 줄 세우기 */

    printf("%d\n", MAXANS);

    return 0;
}

 

visit 배열을 이용해 선택된 번호는 다시 선택하지 않도록 하고, L이 10이 될 때 종료한다.

그러면 list[1] ~ list[9]까지 선수들의 번호가 저장이 된다.

실제 선수 1번은 list[4]에만 존재하므로, simulate 전에 list[1]과 list[4]를 변경하면 list[4]는 항상 1이 된다.

simulate 종료 후에는 다음 경우의 수를 위해 list[4]와 list[1]의 번호를 바꿔서 원래대로 만든다.

int list[10 + 5];
int visit[10 + 5];

void outputList()
{
    for (int i = 1; i <= 9; i++) printf("%d ", list[i]);
    putchar('\n');
}

int MAXANS = 0;
void DFS(int L)
{
    if (L > 9)
    {   
        int tmp;

        list[1] = list[4]; 
        list[4] = 1; /* 1번 선수는 항상 4번 위치에 */

        //outputList();
        tmp = simulate();
        if (MAXANS < tmp) MAXANS = tmp;

        list[4] = list[1];
        list[1] = 1; /* 원래대로 복구 */

        return;
    }

    for (int p = 2; p <= 9; p++)
    {
        if (visit[p] == 1) continue;

        list[L] = p;

        visit[p] = 1;
        DFS(L + 1);
        visit[p] = 0;
    }
}

이제 경우의 수가 만들어졌으니, simulate 함수로 야구 게임을 해본다.

---

simulate 함수는 SCORE = 0으로 초기화한 후에, 각 이닝을 N번 진행하고 최종 SCORE를 return한다.

가장 처음으로 공을 던지는 순서는 list[player = 1]이므로 1번 부터 시작한다.

int simulate()
{
    SCORE = 0;

    int player = 1;
    for (int inning = 1; inning <= N; inning++)
    {
        player = simulateInning(inning, player);
    }

    return SCORE;
}

 

simulateInning은 각 이닝을 시뮬레이션해서 SCORE에 점수를 누적하고, 마지막 player를 return한다.

그러면 simulate에서 list[player]가 다음 simulateInning의 시작 선수가 된다.

"타순은 이닝이 변경되어도 순서를 유지해야 한다." 조건 때문에 필요한 구현이다.

 

1 ~ 3루는 position 배열에 선수가 있는지 없는지 check하도록 한다.

선수의 결과가 OUT이라면 count를 세고, HOMERUN이라면 position에 있는 모든 선수와 자신을 SCORE에 더한다.

 

안타 ~ 3루타의 경우에는 주자를 포함하여 position에서 1 ~ 3만큼 옮긴다.

이 때, 3을 넘어가면 한 바퀴를 돌았으므로 SCORE를 더해주고 position은 0으로 변경한다.

타자의 경우는 나온 결과에 대해 position[result]에 1을 표시하면 된다.

 

점수 계산이 끝나면 playerNumber를 올리고, 종료가 될 경우에는 playerNumber를 return한다.

int SCORE;

int simulateInning(int inning, int startPlayerNumber)
{
    int position[5] = { 0 };
    int currentPlayer, playerNumber, outCount;

    outCount = 0;
    playerNumber = startPlayerNumber;
    while (1)
    {
        currentPlayer = list[playerNumber];
        int result = player[inning][currentPlayer];

        if (result == OUT) outCount++;
        else if (result == HOMERUN)
        {
            int cnt = 0;
            for (int i = 1; i <= 3; i++)
            {
                cnt += position[i];
                position[i] = 0;
            }

            SCORE += (cnt + 1); /* 타자 포함 */
        }
        else /* 1 ~ 3 */
        {
            for (int i = 3; i >= 1; i--)
            {
                if (position[i])
                {
                    if (i + result > 3) SCORE++;
                    else position[i + result] = 1;

                    position[i] = 0;
                }
            }

            position[result] = 1;
        }

        playerNumber++;
        if (playerNumber == 10) playerNumber = 1;
        if (outCount == 3) break;
    }

    return playerNumber;
}

 

시뮬레이션이 끝나면 DFS에서 SCORE를 갱신하면 된다.

최종 코드는 아래를 참고하자.

#include <stdio.h>

#define MAX (50 + 5)

#define OUT (0)
#define HOMERUN (4)

int N;
int player[MAX][15];
int list[10 + 5];
int visit[10 + 5];
int SCORE;

void input()
{
	scanf("%d", &N);

	for (int i = 1; i <= N; i++)
		for (int k = 1; k <= 9; k++)
			scanf("%d", &player[i][k]);
}

void outputList()
{
	for (int i = 1; i <= 9; i++) printf("%d ", list[i]);
	putchar('\n');
}

int simulateInning(int inning, int startPlayerNumber)
{
	int position[5] = { 0 };
	int currentPlayer, playerNumber, outCount;

	outCount = 0;
	playerNumber = startPlayerNumber;
	while (1)
	{
		currentPlayer = list[playerNumber];
		int result = player[inning][currentPlayer];

		if (result == OUT) outCount++;
		else if (result == HOMERUN)
		{
			int cnt = 0;
			for (int i = 1; i <= 3; i++)
			{
				cnt += position[i];
				position[i] = 0;
			}

			SCORE += (cnt + 1); /* 타자 포함 */
		}
		else /* 1 ~ 3 */
		{
			for (int i = 3; i >= 1; i--)
			{
				if (position[i])
				{
					if (i + result > 3) SCORE++;
					else position[i + result] = 1;

					position[i] = 0;
				}
			}

			position[result] = 1;
		}

		playerNumber++;
		if (playerNumber == 10) playerNumber = 1;
		if (outCount == 3) break;
	}

	return playerNumber;
}

int simulate()
{
	SCORE = 0;

	int player = 1;
	for (int inning = 1; inning <= N; inning++)
	{
		player = simulateInning(inning, player);
	}

	return SCORE;
}

int MAXANS = 0;
void DFS(int L)
{

	if (L > 9)
	{
		int tmp;

		list[1] = list[4];
		list[4] = 1;

		//outputList();
		tmp = simulate();
		if (MAXANS < tmp) MAXANS = tmp;

		list[4] = list[1];
		list[1] = 1;

		return;
	}

	for (int p = 2; p <= 9; p++)
	{
		if (visit[p] == 1) continue;

		list[L] = p;

		visit[p] = 1;
		DFS(L + 1);
		visit[p] = 0;
	}
}

int main(void)
{
	input();

	list[1] = 1;
	DFS(2);

	printf("%d\n", MAXANS);

	return 0;
}