boj, 백준) 17281. ⚾ ( C / C++)

1. 문제 링크

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

17281번: ⚾

2. 문제 개요

 매 이닝 타자들의 결과를 알고 있을 때, 타순을 적절히 짜서 얻을 수 있는 최대 점수를 구할 것.

 

3. 문제 힌트

 DFS -> 순열문제. 모든 테스트 케이스를 검사해보기. 

타순을 정하고, 주어진 룰을 기반으로 시뮬레이션 해보기.

 

구현 능력에 따라 어려운 사람도 있을 것이고 쉬운 사람도 있다고 생각함.

얼마나 생각을 코드로 잘 옮기느냐가 관건.

 

4. 문제 풀이

 우선 맵을 입력받고, dfs함수를 실행한다.

dfs함수의 depth가 4인경우(4번 타자를 정하는 dfs), 1번타자를 4번타자 자리에 넣을 수 있게 따로 조건문을 만들어둔다.

그리고 문제에 정의된 규칙대로 빠짐없이 구현한다. 즉, 정해진 타순마다 야구게임을 다 해보는 것과 마찬가지.

 

문제를 잘 이해하고 야구의 규칙을 자신의 것으로 만든다면, 충분히 쉽게 풀 수 있을 거라고 생각한다.

 

 

5. 코드

#include <stdio.h>

int n;
int hit[51][10];
int order[10];
int num[] = { 0,0,1,1,1,1,1,1,1,1 };
int ret = -0x7fffffff;
void dfs(int depth)
{
	if (depth == 4)
	{
		order[depth] = 1;
		dfs(depth + 1);
	}
	if (depth == 10)
	{
		int thisscore = 0;

		int next = 1;

		for (int i = 1; i <= n; i++)
		{
			bool base[4] = { false, };
			int getscore = 0;
			int outcount = 0;
			//i번째 이닝..
			while (outcount != 3)
			{
				
				if (hit[i][order[next]] == 0)
				{
					outcount++;
					
				}
				else if (hit[i][order[next]] == 1)
				{
					if (base[3] == true)
						getscore++;
					base[3] = false;

					if (base[2])
					{
						base[2] = false;
						base[3] = true;
					}
					if (base[1])
					{
						base[1] = false;
						base[2] = true;
					}
					base[1] = true;
				}
				else if (hit[i][order[next]] == 2)
				{
					for (int i = 2; i <= 3; i++)
						if (base[i])
							getscore++;

					for (int i = 2; i <= 3; i++)
						base[i] = false;

					base[2] = true;

					if (base[1] == true)
					{
						base[1] = false;
						base[3] = true;
					}
						
				}
				else if (hit[i][order[next]] == 3)
				{
					//주자
					for (int i = 1; i <= 3; i++)
						if (base[i])
							getscore++;
					for (int i = 1; i <= 3; i++)
						base[i] = false;
					base[3] = true;
				}
				else if (hit[i][order[next]] == 4)
				{
					//주자
					for (int i = 0; i <= 3; i++)
						if (base[i])
							getscore++;
					//타자
					getscore++;
					for (int i = 1; i <= 3; i++)
						base[i] = false;
				}
				next = (next % 9) + 1;
			}
			outcount = 0;
			thisscore += getscore;
		}
		if (ret < thisscore)
			ret = thisscore;

		return;
	}

	//순열.
	for (int i = 0; i <= 9; i++)
	{
		num[i]--;
		if (num[i] >= 0)
		{
			order[depth] = i;
			dfs(depth + 1);
			order[depth] = 0;
		}
		num[i]++;
	}
}

int main(void)
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= 9; j++)
				scanf("%d", &hit[i][j]);
		
	dfs(1);

	printf("%d", ret);

	return 0;
}

6. 결과 사진

지적, 댓글 언제나 환영입니다~