[백준 17281] 야구

분류 

dfs, 구현

요구사항

각 라운드별 선수의 타율이 주어졌을 때, 최고 점수를 얻을 수 있도록 타순 정하기

풀이

1. 타순 정하기

 - 타순은 dfs로 구현할 수 있도록 한다.

 - visit와 play 이용

 - 4번째 선수는 항상 1번

2. 게임 진행

 - 주어진 공식에 따라서 구현한다

 

dfs(1)로 시작해야하는데 dfs(0)으로 시작하여서 한참을 고민했다

dfs(0)으로 해도

visit[1]은 1이니깐 적용 안되고 그 다음부터 시작하니깐 보기에 있는 것은 다 맞았다

설계대로 되는지 검증하기

 

#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
int visit[10];
int play[10];
int map[55][11];
int n;
int house[5];
int ans = 0;
int Anta() {
	int nowscore = 0;
	if (house[3] == 1) {
		house[3] = 0;
		nowscore++;
	}
	if (house[2] == 1) {
		house[3] = 1;
		house[2] = 0;
	}
	if (house[1] == 1) {
		house[2] = 1;
		house[1] = 0;
	}
	house[1] = 1;
	return nowscore;
}
int TwoRoo() {
	int nowscore = 0;
	if (house[3] == 1) {
		house[3] = 0;
		nowscore++;
	}
	if (house[2] == 1) {
		nowscore++;
		house[2] = 0;
	}
	if (house[1] == 1) {
		house[3] = 1;
		house[1] = 0;
	}
	house[2] = 1;
	return nowscore;
}
int ThreeRoo() {
	int nowscore = 0;
	if (house[3] == 1) {
		house[3] = 0;
		nowscore++;
	}
	if (house[2] == 1) {
		nowscore++;
		house[2] = 0;
	}
	if (house[1] == 1) {
		nowscore++;
		house[1] = 0;
	}
	house[3] = 1;
	return nowscore;
}
int HomeRun() {
	int nowscore = 0;
	if (house[3] == 1) {
		house[3] = 0;
		nowscore++;
	}
	if (house[2] == 1) {
		nowscore++;
		house[2] = 0;
	}
	if (house[1] == 1) {
		nowscore++;
		house[1] = 0;
	}
	nowscore++;
	return nowscore;
}

int Game(int arr[]) {
	//memset(house, 0, sizeof(house));
	int turn = 1;
	int round = 1;
	int score = 0;
	int cnt = 0;
	while (true) {
		if (round == n + 1)
			break;
		int out = 0;
		//한 라운드
		memset(house, 0, sizeof(house));
		while (true) {
			if (map[round][arr[turn]] == 0) 
				out++;
			else if (map[round][arr[turn]] == 1)
			{
				if (house[3] == 1) {
					house[3] = 0;
					score++;
				}
				if (house[2] == 1) {
					house[3] = 1;
					house[2] = 0;
				}
				if (house[1] == 1) {
					house[2] = 1;
					house[1] = 0;
				}
				house[1] = 1;
			}
			else if (map[round][arr[turn]] == 2)
			{
				if (house[3] == 1) {
					house[3] = 0;
					score++;
				}
				if (house[2] == 1) {
					score++;
					house[2] = 0;
				}
				if (house[1] == 1) {
					house[3] = 1;
					house[1] = 0;
				}
				house[2] = 1;
			}
			else if (map[round][arr[turn]] == 3)
			{
				if (house[3] == 1) {
					house[3] = 0;
					score++;
				}
				if (house[2] == 1) {
					score++;
					house[2] = 0;
				}
				if (house[1] == 1) {
					score++;
					house[1] = 0;
				}
				house[3] = 1;
			}
			else if (map[round][arr[turn]] == 4)
			{
				if (house[3] == 1) {
					house[3] = 0;
					score++;
				}
				if (house[2] == 1) {
					score++;
					house[2] = 0;
				}
				if (house[1] == 1) {
					score++;
					house[1] = 0;
				}
				score++;
			}

			turn++;
			if (turn == 10)
				turn = 1;
			if (out == 3)
				break;
		}
		round++;
	}
	return score;
}
int ccnt = 0;
void dfs(int cnt) {
	if (cnt == 4) {
		play[4] = 1;
		dfs(cnt + 1);
		return;
	}
	if (cnt == 10) {
		ccnt++;
		int now = Game(play);
		if (ans < now) {
			ans = now;
		}
		return;
	}
	//i는 타순
	for (int i = 2; i <= 9; i++) {
		if (visit[i] == 0) {
			visit[i] = 1;
			play[cnt] = i;
			dfs(cnt + 1);
			visit[i] = 0;
		}
	}
}
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= 9; j++) {
			scanf("%d", &map[i][j]);
		}
	}
	visit[1] = 1;
	dfs(1);
	printf("%d\n", ans);
//	cout << ccnt << endl;
}