[C++] 백준 17281 야구

문제 링크

---

www.acmicpc.net/problem/17281

17281번: ⚾

 

접근 방법

---

문제 풀이보다 문제를 이해하는데 어려운 문제였다.

 

문제를 간략히 정리하자면

1. 타자들의 순번을 정한다.

2. 1번 선수는 항상 4번째 순서에 와야한다.

3. 아웃이 3번 될 때까지 현재 순열을 반복하여 점수를 더한다.

4. 아웃이 3번 된다면 다음 타자의 순번을 구한다.

5. 모든 이닝이 끝날 때 까지 반복하여 게임의 총 점수를 구한다.

6. 점수의 최대 값을 갱신하며 위의 과정을 반복한다.

 

코드를 단계 별로 보자면

1. DFS를 통해 순열을 구한다. 이 때 cnt=3(4번 타자)는 고정이므로 pass하고, 순열이 완성 되었을 때 게임의 점수를 구하는 play_game()함수를 실행한다.

int solve(int cnt) {

	int maximum = 0;

	if (cnt == 3) //4번 타자는 pass
		cnt++;
	if (cnt == 9) {
		return play_game();
	}
	for (int i = 0; i < 9; i++) {
		if (!visited[i]) { //방문 여부
			visited[i] = true;
			seq[cnt] = i;
			maximum = max(maximum, solve(cnt + 1));
			visited[i] = false;
		}
	}
	return maximum;
}

2. while문을 통해 한 이닝이 끝났을 때 점수(sum)를 더해주며, 다음 이닝의 선두주자(now)를 갱신한다. 

int play_game() { //순서가 결정 되었을 때

	int inning = -1;
	int now = 0;
	int sum = 0;

	while (++inning < N) {
		pair<int, int> info = oneInning(inning, now);
		sum += info.first;
		now = info.second;
	}
	return sum;
}

3. base는 홈 부터 1,2,3루를 의미하며, 아웃(info[inning][hitter] == 0)인 경우 변수out을 증가시켜 반복한다. out이 아니라면 각각의 타자가 친 정보를 통해 move()함수를 실행하여 base를 갱신하며 점수를 구한다.

pair<int, int> oneInning(int inning, int idx) { 
	
	int out = 0;
	int score = 0;

	vector<bool> base = {1,0,0,0};

	while(out < 3) {

		int hitter = seq[idx];
		base[0] = true; //타자 투입

		if (info[inning][hitter] == 0)
			out++;
		else
			score += move(base, info[inning][hitter]);

		idx = (idx + 1) % 9;
	}
		
	return { score, idx };

}

4. 타자의 n루타의 정보를 통해 점수를 얻을 수 있는 상황(next >= 4)에는 score를 획득하며, 아닌 경우에는 루의 위치를 변경시켜준다. 

int move(vector<bool> &base, int scoretype) { 

	int score = 0;

	for (int i = 3; i >= 0; i--) {
		if (base[i]) {
			int next = i + scoretype;
			if (next >= 4) {
				score++;
				base[i] = false;
			}				
			else {
				base[next] = true;
				base[i] = false;
			}
		}
	}
	return score;
}

 

소스 코드

---

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool visited[9];
int seq[10];
int info[51][9];
int N;

int move(vector<bool> &base, int scoretype) { 

	int score = 0;

	for (int i = 3; i >= 0; i--) {
		if (base[i]) {
			int next = i + scoretype;
			if (next >= 4) {
				score++;
				base[i] = false;
			}				
			else {
				base[next] = true;
				base[i] = false;
			}
		}
	}
	return score;
}

pair<int, int> oneInning(int inning, int idx) { 
	
	int out = 0;
	int score = 0;

	vector<bool> base = {1,0,0,0};

	while(out < 3) {

		int hitter = seq[idx];
		base[0] = true; //타자 투입

		if (info[inning][hitter] == 0)
			out++;
		else
			score += move(base, info[inning][hitter]);

		idx = (idx + 1) % 9;
	}
		
	return { score, idx };

}

int play_game() { //순서가 결정 되었을 때

	int inning = -1;
	int now = 0;
	int sum = 0;

	while (++inning < N) {
		pair<int, int> info = oneInning(inning, now);
		sum += info.first;
		now = info.second;
	}
	return sum;
}

int solve(int cnt) {

	int maximum = 0;

	if (cnt == 3)
		cnt++;
	if (cnt == 9) {
		return play_game();
	}
	for (int i = 0; i < 9; i++) {
		if (!visited[i]) {
			visited[i] = true;
			seq[cnt] = i;
			maximum = max(maximum, solve(cnt + 1));
			visited[i] = false;
		}
	}
	return maximum;
}

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> N;

	for (int i = 0; i < N; i++) 
		for (int j = 0; j < 9; j++) 
			cin >> info[i][j];

	visited[0] = true;
	seq[3] = 0;

	cout << solve(0);
}

개발 환경 : VS2017

질문, 지적 환영합니다!