[백준][C++] 17281: ⚾

문제 링크: https://www.acmicpc.net/problem/17281

 

대충 풀고 나서 속도가 넘 안나오길래(336ms) 이것 저것 바꿔봤는데 조금밖에 안줄었습니다.(272ms)

배열 행이랑 열 순서가 달라서 memory locality 때문에 아마 그런 것 같은데... 바꾸기 귀찮으니 그냥 넘어가겠습니다.

 

이 문제는 브루트포스로 풀어야 합니다. 가능한 모든 타순을 만들어서 게임을 진행해보고, 그 점수 중 max값을 출력하면 끝입니다.

타순을 만들 때 여러 선택지가 있겠는데, 재귀(백트래킹)로 풀거나 std::next_permutation으로 풀거나 뭐 자유입니다. 저는 std::next_permutation으로 풀었습니다.

순열로 풀 때는 1번 선수를 4번 타자로 고정시키고, 나머지만 돌려봐야 하니 std::next_permutation(v.begin()+1, v.end()) 이런식으로 쓰면 되겠습니다. 자세한건 코드에서 확인해주세요.

#include <bits/stdc++.h>
using namespace std;

int total_inning;
vector<vector<int>> hitter;	// [번호][이닝]

int baseball(const vector<int>& order) {
	int inning = 0;
	int score = 0;
	int tasoon = 0;	// 타순
	int base;	// 1, 2, 3루

	vector<int> order_rev(9);	// 역인덱스
	for (int i = 0; i < 9; ++i)
		order_rev[order[i]] = i;

	while (inning < total_inning) {
		int out = 0;
		base = 0;

		while (out < 3) {
			int action = hitter[order_rev[tasoon]][inning];
			
			if (action == 0) ++out;
			else {
				base <<= action;
				base |= (1 << (action - 1));
				score += __builtin_popcount(base & ~(0x7));
				base = base & 0x7;
			}

			tasoon = (tasoon == 8 ? 0 : tasoon+1);	// tasoon = (tasoon+1) % 9 보다 약간 빠름
		}

		++inning;
	}

	return score;
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);

	cin >> total_inning;

	hitter = vector<vector<int>>(9, vector<int>(total_inning));
	for (int i = 0; i < total_inning; ++i) {
		for (int j = 0; j < 9; ++j) {
			cin >> hitter[j][i];
		}
	}

	vector<int> order{ 3,0,1,2,4,5,6,7,8 };

	int max_score = 0;
	do {
		max_score = max(max_score, baseball(order));
	} while (next_permutation(order.begin()+1, order.end()));
	cout << max_score << '\n';

	return 0;
}

중간에 타순 8->0으로 갈 때 보통 저렇게 tasoon = (tasoon+1) % 9 썼는데, 저렇게 삼항연산자나 분기문 써서 처리하는게 더 빠르다고 하더라고요?

그래서 한 번 써봤습니다. 정말 실행속도가 조금 빨라지긴 했습니다. 근데 귀찮아서 앞으로는 저렇게 안할듯 합니다.

배열 인덱스 실수하기 참 좋은 문제네요