백준 17281번: ⚾ (C++)

1. 문제 링크

17281번: ⚾

2. 소스코드

#include <iostream>
#include <string>
#include <algorithm>
#define MAX_N 51
using namespace std;
int ans = 0;
int hit[MAX_N][9];
int base[4];
int main() {
	int innings = 1;
	int index = 0;//타순
	int number; //선수 번호
	int n;
	cin >> n;
	string order = "12345678"; //**주의** 1~3: 1~3번째 타자, 4~8: 5~9번째 타자
	int out = 0;
	int score;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < 9; j++) {
			cin >> hit[i][j];
		}
	}
	do {
		score = 0;
		innings = 1;
		index = 0;
		while (innings <= n) {
        	//4번 타자는 1번 선수
			if (index == 3)number = 0;
			else if (index > 3)number = order[index - 1]-'0';
			else number = order[index]-'0';
			if (hit[innings][number] == 0) {
				out++;
				if (out == 3) {
					base[0] = base[1] = base[2]=base[3] = 0;
					innings++;
					out = 0;
				}
			}
			else {
				int d = hit[innings][number];
				base[0] = 1;
				for (int b = 3; b >= 0; b--) {
					if (base[b] == 1) {
						if ((b + d) > 3) {
							score++;
						}
						else {
							base[b + d] = 1;
						}
						base[b] = 0;
					}
				}
			}
			index = (index + 1) % 9;
		}
		if (ans < score)ans = score;
	} while (next_permutation(order.begin(), order.end()));
	cout << ans;
	return 0;
}

3. 노트

3-1.next_permutation을 이용한 순열의 구현

C++의 에는 next_permutation이라는 함수가 있다. 이 함수는 컨테이너의 시작 iterator와 끝 iterator를 인자로 받아 컨테이너의 원소를 해당 순열 순서로 바꾸고 true를 반환한다. 이 때 next_permutation을 사용하여 모든 가능한 수열을 출력하려면 컨테이너가 오름차순으로 정렬되어 있어야 한다.

next_permutation의 특징
기본적으로 오름차순으로 순열을 생성한다.
->내림차순으로 순열을 생성할 때에는 내림차순으로 정렬된 데이터로 prev_permutation을 사용하여야 한다.
컨테이너에 중복된 원소가 존재할 경우, 중복되는 순열들은 제외한다.

3-2.Brute force

문제를 brute force로 해결하려고 할 경우 시간 초과에 주의하여야 한다. 보통 제한시간 1초당 1억(10^8)번의 연산이 가능하다.
문제에서 타순은 8!=40,320가지가 존재하고, 각 이닝에는 아웃을 기록하는 타자가 적어도 한 명 존재하므로 최악의 경우 50이닝3(아웃 수)1(아웃을 기록하는 타자)=150회의 연산이 필요하다.따라서 최악의 경우 40320*150=6,048,000회의 연산이 필요하므로, 충분히 모든 경우를 확인할 수 있다.