[알고리즘] ⚾ (백준, 17281)

문제

17281번: ⚾

 

 

풀이

ruhz3/CodingTest

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

int N;
int hitTable[50][9];
int entry[9];
vector<int> field;

int findMaxScore() {
	int outCount;
	int entryIdx = 0;
	int score = 0;

	for (int inning = 0; inning < N; inning++) {
		// 이닝이 시작되면, outCount와 필드 초기화
		outCount = 0;
		field.clear();
		while (outCount < 3) {
			int hitScore = hitTable[inning][entry[entryIdx]];
			// 현재 선수 아웃을 친 경우
			if (hitScore == 0) {
				outCount++;
			}
			// 현재 선수 안타를 친 경우
			else {
				// 선수 한 명을 넣어주고, 필드 위의 모든 선수 진루
				field.push_back(0);
				for (int i = 0; i < field.size(); i++) {
					field[i] += hitScore;
				}
				// 필드 위에 4이상인 선수 빼주면서 점수++
				while(!field.empty() && field[0] >= 4) {
					field.erase(field.begin());
					score++;
				}
			}
			// 다음 선수 입장
			if (entryIdx == 8) entryIdx = 0;
			else entryIdx++;
		}
	}
	return score;
}

int makeEntry(int entryNum){
	// entry가 완성되면 findMaxScore() 호출
	if (entryNum == 9) {
		return findMaxScore();
	}
	// 3번타자는 0번선수 고정
	if (entryNum == 3) {
		entry[3] = 0;
		return makeEntry(entryNum + 1);
	}
	
	int res = 0;
	bool flag;
	for (int i = 1; i < 9; i++) {
		// 0번 선수 제외, 이전 entry에 넣으려는 선수가 있는지 검사해 flag 저장
		flag = true;
		for (int j = 0; j < entryNum; j++) {
			if (i == entry[j])
				flag = false;
		}
		// 없다면 선수를 해당 entry에 넣고 다음 entry 작성
		if (flag) {
			entry[entryNum] = i;
			res = max(res, makeEntry(entryNum + 1));
		}
	}
	return res;
}

int main() {
	memset(entry, -1, sizeof(entry));
	cin >> N;
	for (int inning = 0; inning < N; inning++)
		for (int player = 0; player < 9; player++)
			cin >> hitTable[inning][player];

	cout << makeEntry(0) << endl;
	return 0;
}

어차피 게임의 룰은 바뀌지 않기 때문에 규칙에 맞게 게임을 플레이 하는 함수를 만들고, 선수의 엔트리를 재귀로 완전탐색해서 구현하고자 했다. 사소한 부분에서 막혀 시간을 오래 썼지만, 문제가 적당한 난이도여서 재미있게 풀었던 것 같다.

<makeEntry 함수>
- 선수의 entry를 재귀로 완전탐색한다.
- entry를 모두 구성하고 나면, findMaxScore함수를 호출하여 return한다.
- 백트래킹하며, 호출한 재귀함수의 return값들을 비교하고 가장 큰 값을 반환해서 가장 큰 값을 찾는다.​

<findMaxScore 함수>
- 각 이닝 별로 while 반복문 안에 들어가고, outCount가 3이상 늘어나면 빠져나온다.
- 필드는 벡터로 구성했고, 이닝이 끝나도 다음 타석에 오를 선수 정보가 보존되게 구현했다.
  Out이라면 :
   - outCount 1증가 및 다음 선수로 넘김
  Out이 아니라면 :
   - 일단 선수를 0루(홈)에 넣고, n루타라면 벡터(필드)에 있는 모든 원소들에 n을 더한다(진루).
   - 4이상인 경우 벡터(필드)에서 빼주고 score++
   - 다음 선수로 넘김