백준 17281 - ⚾
Updated:
C++
17281 번 - ⚾
문제
한 야구팀의 감독 아인타는 타순을 정하려고 한다. 아인타 팀의 선수는 총 9명이 있고, 1번부터 9번까지 번호가 매겨져 있다. 아인타는 자신이 가장 좋아하는 선수인 1번 선수를 4번 타자로 미리 결정했다. 이제 다른 선수의 타순을 모두 결정해야 한다. 아인타는 각 선수가 각 이닝에서 어떤 결과를 얻는지 미리 알고 있다. 가장 많은 득점을 하는 타순을 찾고, 그 때의 득점을 구해보자.
접근 방법
세 부분으로 나누어 접근하였다.
- 각 타자들의 타순을 정한다
- 정한 타순으로 경기를 진행한다.
- 각 타자가 안타를 쳤을 시에 주자를 설정하고, 홈에 들어 오면 점수를 낸다.
안타는 1,2,3루타 그리고 홈런을 쳤다는 것을 모두 표현한 것이다.
구현
Main()
선수들의 각 이닝당 타격 능력을 status 2차원 배열에 저장한다.
status[a][b]의 a는 각 이닝을 뜻하고, b는 그 선수가 a이닝에서 타격을 할 수 있는 능력을 뜻한다.
status[3][1] => 2 라는 것은 현재 배열의 첫번째에 있는 b의 선수가 3이닝에는 2루타를 계속 친다는 뜻이다.
DFS()
order 배열은 타순을 의미한다.
order[4] = 1은 이 경기에서 4번째 타석은 status의 첫 번째 선수가 뽑혔다는 것이다.
order 배열의 1~9 까지 선수를 배정하여 타석을 정하고 각 order의 값에 따라 status에 대입하여 그 선수의 타격 능력을 확인한다.
타순을 정하는 방법은 DFS를 이용하였다.
lv은 각 타순을 의미하며, lv이 1이면 첫번째 타석이라는 뜻이다.
즉 order[lv] = 3에서 lv가 5라면, 5번째 타석에 status 3번의 선수가 타석에 선다는 뜻이다.
DFS를 빠져나가는 조건으로 선수가 9명이 뽑혔을 경우를 판단하며 이는 lv == 10이다.
이는 lv이 처음에 1에서 시작하므로 9명이 뽑히면 lv가 10이 되기 때문이다.
PlayGame()
각 선수를 정한 타석으로 경기를 진행한다. while문 3개로 경기를 표현하였는데, while문 하나 당
- 각 이닝
- 아웃 카운트
- 각 타석 을 뜻한다.
각 이닝은 n이며, 아웃 카운트는 3개가 되면 종료된다. 또한 각 타석은 선수가 out을 반환할 때 까지 반복한다.
Hit(int 안타 종류)
선수가 안타를 쳤을 시에, 이 함수를 통해 주루 플레이를 구현한다.
보통 다른 블로그들은 직관적인 배열을 사용하는데, 나는 queue를 사용하였다.
player의 값은 주자들을 표현하며,
player에 {3, 2} 가 순서대로 들어있으면, 3루, 2루에 주자가 있다는 것을 의미한다.
인자 값을 통해 주자를 이동시키며, 새로운 주자를 등록한다.
위의 경우에서 1루타가 쳤다는 값이 들어오면, player의 {3, 2}를 1씩 증가시키고 새로이 1을 등록한다.
이는 3은 4가 되어 홈에 들어와 score를 1 증가시키고, 2는 3으로 증가시킨다.
이후 player는 {3 , 1}이 된다.
주의
만약 3아웃이 되면, 주자는 다 없어져야 하므로, 전역 변수로 설정 되어 있는 player 함수를 비워준다.
코드
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
int n;
int status[51][10]; //각 이닝 별, 선수들의 타격 능력
int order[10]; //실제 타순을 저장함
int visited[10]; //이미 뽑은 선수인지 아닌자 확인
int score; //각 타순 별 경기 점수
int result = 0; //최종 점수(제일 높은)
queue<int> player;
void DFS(int lv); //타순을 결정하는 함수
void PlayGame(); //배정된 타순에 따라 경기
void hit(int run); //각 선수가 안타를 쳤을 시에 계산 방법
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= 9; j++) {
cin >> status[i][j];
}
}
visited[1] = true; //첫번째 선수는 4번에 고정
order[4] = 1;
DFS(1);
cout << result;
return 0;
}
void DFS(int lv) {
if (lv == 10) {
PlayGame(); //뽑은 타순으로 경기 시작!
return;
}
else if (lv == 4) { //lv이 4라는 것은 4번 타자이며, 이미 배정되어 있으므로 5번 타순을 결정하도록 넘어감
DFS(lv + 1);
return;
}
for (int i = 2; i <= 9; i++) { //첫번째 선수는 4번에 고정 되어 있으므로 두번재부터 아홉 번째 선수까지 타순 지정
if (!visited[i]) {
visited[i] = true;
order[lv] = i; //각 선수를 타순에 지정한다. lv이 타순, i가 선수
DFS(lv + 1);
visited[i] = false;
}
}
}
void PlayGame() {
int outCnt = 0;
int ining = 1;
int idx = 1;
int curPlr = order[1];
while (ining != (n+1)) { //주어진 이닝 만큼 반복
while (outCnt != 3) { //아웃 카운트가 3이면 끝
while (status[ining][curPlr] != 0) { //각 타순 별로 정해진 능력치를 본다. 0이면 아웃이므로 다음 타순
switch (status[ining][curPlr]) {
case 1:
hit(1); // 1루타
break;
case 2:
hit(2); // 2루타
break;
case 3:
hit(3); // 3루타
break;
case 4:
hit(4); // 홈런
break;
}
idx++; //타순 증가
if (idx == 10) //9번 타자 다음은 1번 타자
idx = 1;
curPlr = order[idx]; //타순에 따라 선수 배정
}
outCnt++; //아웃
idx++; //아웃 당한 후 다음 타자를 부르기 위한 작업
if (idx == 10)
idx = 1;
curPlr = order[idx];
}
while (!player.empty()) //아웃이 되었으면, 주자가 없어야 하므로, 삭제
player.pop();
outCnt = 0;
ining++; //이닝 끝
}
//한 게임 종료
result = max(result, score);
score = 0;
}
//안타 계산
void hit(int run) {
int temp;
if (player.empty()) { //주자에 아무도 없을 시
if (run != 4) //홈런이 아니라면 진루
player.push(run);
else
score++; //홈런이면 점수 1점 획득
return;
}
int size = player.size();
for (int i = 0; i < size; i++) { //현재 주루 상황에서 각 안타에 따라 주자 진루
temp = player.front();
player.pop();
temp += run;
if (temp >= 4) { // 4 이상이면 홈이므로 점수 증가
score++;
}
else
player.push(temp);
}
if (run != 4) //안타를 친 주자도 진루
player.push(run);
else //홈런이면 점수 획득
score++;
}
후기 및 개선할 점
후기: 4달 전에 못 푼 문제를 자력으로 풀어서 기쁘다. 하지만 거의 낮 시간을 다 써서 풀었다. 그렇게 어려운 문제는 아니었는데..
