(c++)백준 17281번: ⚾

www.acmicpc.net/problem/17281

17281번: ⚾

[풀이]

dfs 순열 구하는 방법을 이용하여 타순을 구하고 게임 룰대로 시뮬레이션 하면 되는 문제였다.

1. 타순 구하기: 순열

2. 각 타순에 대하여 나올 점수 구하기

3. 최댓값 갱신

※다음 이닝으로 넘어갈 조건, 타순 만드는 조건 등 주위깊게 보기!

 

#include <iostream>
#include <algorithm>
using namespace std;

int N;
int Results[50][10];
int Order[10];
bool check[10];
int Max = -1;
int Ru1 = 0, Ru2 = 0, Ru3 = 0;

int cal_score() {
	int score = 0;
	int out = 0;
	int start_p = 1;
	bool go_next_ining = false;
	for (int i = 0; i < N; i++) {
		Ru1 = 0, Ru2 = 0, Ru3 = 0;
		out = 0;
		go_next_ining = false;
		while (1) {
			for (int j = start_p; j <= 9; j++) {
				//아웃일 경우
				if (Results[i][Order[j]] == 0)
					out++;
				//안타일 경우
				else if (Results[i][Order[j]] == 1) {
					if (Ru3 == 1) {
						Ru3 = 0;
						score++;
					}
					if (Ru2 == 1) {
						Ru3 = 1;
						Ru2 = 0;
					}
					if (Ru1 == 1) {
						Ru2 = 1;
					}
					Ru1 = 1;
				}
				//2루타일 경우
				else if (Results[i][Order[j]] == 2) {
					if (Ru3 == 1) {
						Ru3 = 0;
						score++;
					}
					if (Ru2 == 1) {
						Ru2 = 0;
						score++;
					}
					if (Ru1 == 1) {
						Ru3 = 1;
						Ru1 = 0;
					}
					Ru2 = 1;
				}
				//3루타일 경우
				else if (Results[i][Order[j]] == 3) {
					if (Ru3 == 1) {
						Ru3 = 0;
						score++;
					}
					if (Ru2 == 1) {
						Ru2 = 0;
						score++;
					}
					if (Ru1 == 1) {
						Ru1 = 0;
						score++;
					}
					Ru3 = 1;
				}
				//홈런일 경우
				else if (Results[i][Order[j]] == 4) {
					if (Ru3 == 1) {
						Ru3 = 0;
						score++;
					}
					if (Ru2 == 1) {
						Ru2 = 0;
						score++;
					}
					if (Ru1 == 1) {
						Ru1 = 0;
						score++;
					}
					score++;
				}
				
				if (out >= 3) {
					start_p = j + 1;
					if (start_p == 10)start_p = 1;
					go_next_ining = true;
					break;
				}
			}
			if (go_next_ining == true)
				break;
			start_p = 1;
		}
	}
	return score;
}

//타순 정하기(순열)->점수 확인
void dfs(int cnt) {
	if (cnt == 10) {
		int res = cal_score();
		Max = max(Max, res);
		return;
	}
	for (int i = 2; i <= 9; i++) {
		if (check[i] == true)
			continue;
		check[i] = true;
		Order[cnt] = i;
		//4번째는 이미 정해져 있으므로 5번째 타자를 정하러 간다.
		if (cnt == 3)
			dfs(cnt + 2);
		else
			dfs(cnt + 1);
		check[i] = false;
	}
}

void solution() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 1; j <= 9; j++) {
			cin >> Results[i][j];
		}
	}
	//1번 타자는 언제나 4번째
	check[1] = true;
	Order[4] = 1;
	dfs(1);
	cout << Max << '\n';
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	solution();
	return 0;
}

+1,2,3루의 주자 상황을 Base배열에 넣고 for문으로 안타, 2루타, 3루타, 홈런 처리 (계산시간이 더 오래걸림)

#include <iostream>
#include <vector>
#include <algorithm>//max
using namespace std;

int N;
int Result[50][10];//각 이닝에서 선수가 얻는 결과
bool check[10];//선수를 배정했는지
int hitter[10];//선수 순서
int Max = -1;

int Game() {
	int score = 0;
	int num = 1;
	for (int i = 0; i < N; i++) {
		int Base[4] = { 0,0,0,0 };//각 베이스에 선수가 있는지
		int Out = 0;
		bool go_next_ining = false;
		while (1) {
			for (int j = num; j <= 9; j++) {
				int h = hitter[j];//이번 타자
				int result = Result[i][h];//이번 이닝 결과
				//아웃이면
				if (result == 0) {
					Out++;
					if (Out >= 3) {
						num = j + 1;
						if (num == 10)
							num = 1;
						go_next_ining = true;
						break;
					}
				}
				/*
				//안타
				else if (result == 1) {
					if (Base[3] == 1) {
						score++;
						Base[3] = 0;
					}
					if (Base[2] == 1) {
						Base[3] = 1;
						Base[2] = 0;
					}
					if (Base[1] == 1) {
						Base[2] = 1;
					}
					Base[1] = 1;
				}
				//2루타
				else if (result == 2) {
					if (Base[3] == 1) {
						score++;
						Base[3] = 0;
					}
					if (Base[2] == 1) {
						score++;
						Base[2] = 0;
					}
					if (Base[1] == 1) {
						Base[3] = 1;
						Base[1] = 0;
					}
					Base[2] = 1;
				}
				//3루타
				else if (result == 3) {
					if (Base[3] == 1) {
						score++;
						Base[3] = 0;
					}
					if (Base[2] == 1) {
						score++;
						Base[2] = 0;
					}
					if (Base[1] == 1) {
						score++;
						Base[1] = 0;
					}
					Base[3] = 1;
				}
				//홈런
				else if (result == 4) {
					if (Base[3] == 1) {
						score++;
						Base[3] = 0;
					}
					if (Base[2] == 1) {
						score++;
						Base[2] = 0;
					}
					if (Base[1] == 1) {
						score++;
						Base[1] = 0;
					}
					//타자
					score++;
				}*/
				else {
					Base[0] = 1;
					for (int b = 3; b >= 0; b--) {
						if (Base[b] == 1) {
							if (b + result >= 4) {
								score++;
								Base[b] = 0;
							}
							else {
								Base[b + result] = 1;
								Base[b] = 0;
							}
						}
					}
				}
			}
			if (go_next_ining == true)
				break;
			num = 1;
		}
	}
	return score;
}

//순열
void setHitter(int cnt) {
	if (cnt == 10) {
		int res = Game();
		Max = max(Max, res);
		return;
	}
	for (int i = 2; i <= 9; i++) {
		if (check[i] == true)
			continue;
		check[i] = true;
		hitter[cnt] = i;
		if (cnt == 3)
			setHitter(cnt + 2);
		else
			setHitter(cnt + 1);
		check[i] = false;
	}
	
}

int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 1; j <= 9; j++) {
			cin >> Result[i][j];
		}
	}
	hitter[4] = 1;
	setHitter(1);
	cout << Max << '\n';
	return 0;
}