알고리즘 풀이/백준(Boj)
백준(BOJ) 17281번 ⚾
100win10
2020. 2. 20. 02:29
문제 :
https://www.acmicpc.net/problem/17281
17281번: ⚾
⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종료되고, 두 팀이 공격과 수비를 서로 바꾼다. 두 팀은 경기가 시작하기 전까지 타순(타자가 타석에 서는 순서)을 정해야 하고, 경기 중에는 타순을 변경할 수 없다. 9번 타자까지 공을 쳤는데 3아웃이 발생하지 않은 상태면 이닝은 끝나지 않고, 1번 타자가 다시 타석에
www.acmicpc.net
풀이 :
첫 주자인 0번은 무조건 4번째에 들어가기 때문에 1~8까지 next_permutation을 통해 순서를 돌려주고
solve 함수를 호출할 때 order에 4번째 순서에 0을 껴넣는 상태로 진행된다.
solve함수는
주자는 이닝이 바뀌어도 초기화 되지 않도록 while문 밖에 begin을 넣어서 해결하였다.
inning [0] [1].. 에 각 0이닝 1이닝에 해당하는 점수들을 넣어 놓았기 때문에 ret으로 불러온 후
0,1,2,3,4 일때를 처리해 주었다.
이때 j는 3루부터 1루로 처리해주어야 중복을 막을 수 있다. 그리고 마지막에는 이번 타자( 이번에 치는 타자 )
를 1로 바꿔주면 된다.
코드 ( C++ )
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <iostream> | |
| #include <vector> | |
| #include <algorithm> | |
| using namespace std; | |
| vector<int> inning[51]; | |
| int n; | |
| // 1 2 3 0 4 5 6 7 8 | |
| int solve(vector<int>& order, int cnt) | |
| { | |
| int score = 0; | |
| int begin = 0; | |
| while (cnt != n) { | |
| int roo[5] = { 0,0,0,0,0 }; | |
| int out = 0; | |
| while (1) { | |
| int ret = inning[cnt][order[begin]]; | |
| if (ret == 0) { | |
| out += 1; | |
| if (out == 3) { | |
| begin++; | |
| if (begin > 8) begin = 0; | |
| break; | |
| } | |
| } | |
| else if (ret == 1) { | |
| for (int j = 3; j >= 1; --j) { | |
| if (roo[j] == 1) { | |
| if (j + 1 >= 4) { | |
| score++; | |
| roo[j] = 0; | |
| } | |
| else { | |
| roo[j + 1] = 1; | |
| roo[j] = 0; | |
| } | |
| } | |
| } | |
| // 이번 타자 | |
| roo[1] = 1; | |
| } | |
| else if (ret == 2) { | |
| for (int j = 3; j >= 1; --j) { | |
| if (roo[j] == 1) { | |
| if (j + 2 >= 4) { | |
| score++; | |
| roo[j] = 0; | |
| } | |
| else { | |
| roo[j + 2] = 1; | |
| roo[j] = 0; | |
| } | |
| } | |
| } | |
| // 이번 타자 | |
| roo[2] = 1; | |
| } | |
| else if (ret == 3) { | |
| for (int j = 3; j >= 1; --j) { | |
| if (roo[j] == 1) { | |
| if (j + 3 >= 4) { | |
| score++; | |
| roo[j] = 0; | |
| } | |
| else { | |
| roo[j + 3] = 1; | |
| roo[j] = 0; | |
| } | |
| } | |
| } | |
| // 이번 타자 | |
| roo[3] = 1; | |
| } | |
| else if (ret == 4) { | |
| score++; | |
| for (int j = 1; j < 4; ++j) { | |
| if (roo[j] == 1) { | |
| roo[j] = 0; | |
| score++; | |
| } | |
| } | |
| } | |
| begin += 1; | |
| if (begin > 8) begin = 0; | |
| } | |
| cnt += 1; | |
| } | |
| return score; | |
| } | |
| int main() | |
| { | |
| cin >> n; | |
| for (int i = 0; i < n; ++i) | |
| { | |
| inning[i].resize(9); | |
| for (int j = 0; j < 9; ++j) { | |
| cin >> inning[i][j]; | |
| } | |
| } | |
| int ans = 0; | |
| vector<int> order = { 1,2,3,4,5,6,7,8 }; | |
| do { | |
| order.insert(order.begin() + 3, 0); | |
| ans = max(ans, solve(order, 0)); | |
| order.erase(order.begin() + 3); | |
| } while (next_permutation(order.begin(), order.end())); | |
| cout << ans << "\n"; | |
| return 0; | |
| } |
