1. 문제
17281번: ⚾
⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종료되고, 두 팀이 공격과 수비를 서로 바꾼다. 두 팀은 경기가 시작하기 전까지 타순(타자가 타석에 서는 순서)을 정해야 하고, 경기 중에는 타순을 변경할 수 없다. 9번 타자까지 공을 쳤는데 3아웃이 발생하지 않은 상태면 이닝은 끝나지 않고, 1번 타자가 다시 타석에
www.acmicpc.net
문제
⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종료되고, 두 팀이 공격과 수비를 서로 바꾼다.
두 팀은 경기가 시작하기 전까지 타순(타자가 타석에 서는 순서)을 정해야 하고, 경기 중에는 타순을 변경할 수 없다. 9번 타자까지 공을 쳤는데 3아웃이 발생하지 않은 상태면 이닝은 끝나지 않고, 1번 타자가 다시 타석에 선다. 타순은 이닝이 변경되어도 순서를 유지해야 한다. 예를 들어, 2이닝에 6번 타자가 마지막 타자였다면, 3이닝은 7번 타자부터 타석에 선다.
공격은 투수가 던진 공을 타석에 있는 타자가 치는 것이다. 공격 팀의 선수가 1루, 2루, 3루를 거쳐서 홈에 도착하면 1점을 득점한다. 타자가 홈에 도착하지 못하고 1루, 2루, 3루 중 하나에 머물러있을 수 있다. 루에 있는 선수를 주자라고 한다. 이닝이 시작될 때는 주자는 없다.
타자가 공을 쳐서 얻을 수 있는 결과는 안타, 2루타, 3루타, 홈런, 아웃 중 하나이다. 각각이 발생했을 때, 벌어지는 일은 다음과 같다.
- 안타: 타자와 모든 주자가 한 루씩 진루한다.
- 2루타: 타자와 모든 주자가 두 루씩 진루한다.
- 3루타: 타자와 모든 주자가 세 루씩 진루한다.
- 홈런: 타자와 모든 주자가 홈까지 진루한다.
- 아웃: 모든 주자는 진루하지 못하고, 공격 팀에 아웃이 하나 증가한다.
한 야구팀의 감독 아인타는 타순을 정하려고 한다. 아인타 팀의 선수는 총 9명이 있고, 1번부터 9번까지 번호가 매겨져 있다. 아인타는 자신이 가장 좋아하는 선수인 1번 선수를 4번 타자로 미리 결정했다. 이제 다른 선수의 타순을 모두 결정해야 한다. 아인타는 각 선수가 각 이닝에서 어떤 결과를 얻는지 미리 알고 있다. 가장 많은 득점을 하는 타순을 찾고, 그 때의 득점을 구해보자.
입력
첫째 줄에 이닝 수 N(2 ≤ N ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에는 각 선수가 각 이닝에서 얻는 결과가 1번 이닝부터 N번 이닝까지 순서대로 주어진다. 이닝에서 얻는 결과는 9개의 정수가 공백으로 구분되어져 있다. 각 결과가 의미하는 정수는 다음과 같다.
- 안타: 1
- 2루타: 2
- 3루타: 3
- 홈런: 4
- 아웃: 0
각 이닝에는 아웃을 기록하는 타자가 적어도 한 명 존재한다.
출력
아인타팀이 얻을 수 있는 최대 점수를 출력한다.
예제 입력 1 복사
2 4 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0
예제 출력 1 복사
1
예제 입력 2 복사
2 4 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0
예제 출력 2 복사
4
예제 입력 3 복사
2 0 4 4 4 4 4 4 4 4 0 4 4 4 4 4 4 4 4
예제 출력 3 복사
43
2. 소스코드
1회차
- 총 경우의 수는 9!으로 362,880.
- 1~9번 선수가 있지만, 1번선수는 무조건 4번타자인 조건이 존재. 정말 단순히 생각해서 1~9 선수를 vector에 담고 next_permutation을 이용, 1번 선수가 4번 타석에 있지 않는 경우는 pass해서 문제를 풀었음.
- 중간에 백트래킹 없이 무조건 모든 순서를 만들고 비교하니, dfs나 bfs에 비해 확실히 속도가 느림.
- 반복이 많다보니 조건문의 사소한 차이에도 시간차가 많이 발생했다.
1) 하드코딩 vs 반복문 (홈런 처리 조건)
- 왼쪽, 오른쪽 코드는 100% 같은 기능이나, 왼쪽으로 구현한 쪽이 20ms 더 빨랐다.
- 조건문이 좀 더 간결하지만, 하드코딩이 더 빠른 경우.
|
if (curHit == HOMERUN) { res++; if (base[0] == 1) { base[0] = 0; res++; } if (base[1] == 1) { base[1] = 0; res++; } if (base[2] == 1) { base[2] = 0; res++; } } |
if (curHit == HOMERUN) { res++; for (int k = 0; k < 3; ++k) { if (base[k] == 1) { base[k] = 0; res++; } } } |
- 어셈블리어
| if (curHit == HOMERUN) { 00320868 cmp dword ptr [ebp-5Ch],4 0032086C jne findMaxPoint+166h (03208F6h) res++; 00320872 mov eax,dword ptr [ebp-18h] 00320875 add eax,1 00320878 mov dword ptr [ebp-18h],eax if (base[0] == 1) { 0032087B mov eax,4 00320880 imul ecx,eax,0 00320883 cmp dword ptr [ebp+ecx-44h],1 00320888 jne findMaxPoint+113h (03208A3h) base[0] = 0; res++; 0032088A mov eax,4 0032088F imul ecx,eax,0 00320892 mov dword ptr [ebp+ecx-44h],0 0032089A mov eax,dword ptr [ebp-18h] 0032089D add eax,1 003208A0 mov dword ptr [ebp-18h],eax } if (base[1] == 1) { 003208A3 mov eax,4 003208A8 shl eax,0 003208AB cmp dword ptr [ebp+eax-44h],1 003208B0 jne findMaxPoint+13Bh (03208CBh) base[1] = 0; res++; 003208B2 mov eax,4 003208B7 shl eax,0 003208BA mov dword ptr [ebp+eax-44h],0 003208C2 mov eax,dword ptr [ebp-18h] 003208C5 add eax,1 003208C8 mov dword ptr [ebp-18h],eax } if (base[2] == 1) { 003208CB mov eax,4 003208D0 shl eax,1 003208D2 cmp dword ptr [ebp+eax-44h],1 003208D7 jne findMaxPoint+161h (03208F1h) base[2] = 0; res++; 003208D9 mov eax,4 003208DE shl eax,1 003208E0 mov dword ptr [ebp+eax-44h],0 003208E8 mov eax,dword ptr [ebp-18h] 003208EB add eax,1 003208EE mov dword ptr [ebp-18h],eax } } 003208F1 jmp findMaxPoint+237h (03209C7h) |
if (curHit == HOMERUN) { 00E60868 cmp dword ptr [ebp-5Ch],4 00E6086C jne findMaxPoint+124h (0E608B4h) res++; 00E6086E mov eax,dword ptr [ebp-18h] 00E60871 add eax,1 00E60874 mov dword ptr [ebp-18h],eax for (int k = 0; k < 3; ++k) { 00E60877 mov dword ptr [ebp-68h],0 00E6087E jmp findMaxPoint+0F9h (0E60889h) 00E60880 mov eax,dword ptr [ebp-68h] 00E60883 add eax,1 00E60886 mov dword ptr [ebp-68h],eax 00E60889 cmp dword ptr [ebp-68h],3 00E6088D jge findMaxPoint+11Fh (0E608AFh) if (base[k] == 1) { 00E6088F mov eax,dword ptr [ebp-68h] 00E60892 cmp dword ptr [ebp+eax*4-44h],1 00E60897 jne findMaxPoint+11Dh (0E608ADh) base[k] = 0; res++; 00E60899 mov eax,dword ptr [ebp-68h] 00E6089C mov dword ptr [ebp+eax*4-44h],0 00E608A4 mov eax,dword ptr [ebp-18h] 00E608A7 add eax,1 00E608AA mov dword ptr [ebp-18h],eax } } 00E608AD jmp findMaxPoint+0F0h (0E60880h) } |
2) while문 vs for문 (안타 처리 조건)
- 왼쪽, 오른쪽 코드는 100% 같은 기능이나, 왼쪽으로 구현한 쪽이 70ms 더 빨랐다.
- while 문에서 변수를 하나더 적게쓰고, 초기화, 대입을 하지않아 차이가 발생.
- while문이 무조건 for문보다 빠르다는 것은 아니다.
- 어셈블리어에서도 확인 가능하다.
- 정말 작은 차이지만 선수 순서마다, 이닝마다, 선수가 안타를 칠때마다 계속 반복되므로 큰 차이가 발생.
|
while(curHit--) { for (int k = 2; k >= 0; --k) { if (k == 2 and base[k] == 1) { res++; base[k] = 0; } else if (k != 2 and base[k] == 1) { base[k + 1]++; base[k] = 0; } } } base[score[i][seq[curBatter]] - 1]++; } |
for(int j = 0; j < curHit ; ++j) { for (int k = 2; k >= 0; --k) { if (k == 2 and base[k] == 1) { res++; base[k] = 0; } else if (k != 2 and base[k] == 1) { base[k + 1]++; base[k] = 0; } } } base[score[i][seq[curBatter]] - 1]++; } |
- 어셈블리어
| while(curHit--) { 010308B4 mov eax,dword ptr [ebp-5Ch] 010308B7 mov dword ptr [ebp-154h],eax 010308BD mov ecx,dword ptr [ebp-5Ch] 010308C0 sub ecx,1 010308C3 mov dword ptr [ebp-5Ch],ecx 010308C6 cmp dword ptr [ebp-154h],0 010308CD je findMaxPoint+1B0h (01030940h) for (int k = 2; k >= 0; --k) { 010308CF mov dword ptr [ebp-74h],2 010308D6 jmp findMaxPoint+151h (010308E1h) 010308D8 mov eax,dword ptr [ebp-74h] 010308DB sub eax,1 010308DE mov dword ptr [ebp-74h],eax 010308E1 cmp dword ptr [ebp-74h],0 010308E5 jl findMaxPoint+1ABh (0103093Bh) if (k == 2 and base[k] == 1) { 010308E7 cmp dword ptr [ebp-74h],2 010308EB jne findMaxPoint+17Dh (0103090Dh) 010308ED mov eax,dword ptr [ebp-74h] 010308F0 cmp dword ptr [ebp+eax*4-44h],1 010308F5 jne findMaxPoint+17Dh (0103090Dh) res++; base[k] = 0; 010308F7 mov eax,dword ptr [ebp-18h] 010308FA add eax,1 010308FD mov dword ptr [ebp-18h],eax res++; base[k] = 0; 01030900 mov eax,dword ptr [ebp-74h] 01030903 mov dword ptr [ebp+eax*4-44h],0 } 0103090B jmp findMaxPoint+1A9h (01030939h) else if(k != 2 and base[k] == 1) { 0103090D cmp dword ptr [ebp-74h],2 01030911 je findMaxPoint+1A9h (01030939h) 01030913 mov eax,dword ptr [ebp-74h] 01030916 cmp dword ptr [ebp+eax*4-44h],1 0103091B jne findMaxPoint+1A9h (01030939h) base[k + 1]++; base[k] = 0; 0103091D mov eax,dword ptr [ebp-74h] 01030920 mov ecx,dword ptr [ebp+eax*4-40h] 01030924 add ecx,1 01030927 mov edx,dword ptr [ebp-74h] 0103092A mov dword ptr [ebp+edx*4-40h],ecx 0103092E mov eax,dword ptr [ebp-74h] 01030931 mov dword ptr [ebp+eax*4-44h],0 } } 01030939 jmp findMaxPoint+148h (010308D8h) } 0103093B jmp findMaxPoint+124h (010308B4h) |
for (int j = 0; j < curHit; ++j) { 00FC08B4 mov dword ptr [ebp-74h],0 00FC08BB jmp findMaxPoint+136h (0FC08C6h) 00FC08BD mov eax,dword ptr [ebp-74h] 00FC08C0 add eax,1 00FC08C3 mov dword ptr [ebp-74h],eax 00FC08C6 mov eax,dword ptr [ebp-74h] 00FC08C9 cmp eax,dword ptr [ebp-5Ch] 00FC08CC jge findMaxPoint+1ACh (0FC093Ch) for (int k = 2; k >= 0; --k) { 00FC08CE mov dword ptr [ebp-80h],2 00FC08D5 jmp findMaxPoint+150h (0FC08E0h) 00FC08D7 mov eax,dword ptr [ebp-80h] 00FC08DA sub eax,1 00FC08DD mov dword ptr [ebp-80h],eax 00FC08E0 cmp dword ptr [ebp-80h],0 00FC08E4 jl findMaxPoint+1AAh (0FC093Ah) if (k == 2 and base[k] == 1) { 00FC08E6 cmp dword ptr [ebp-80h],2 00FC08EA jne findMaxPoint+17Ch (0FC090Ch) 00FC08EC mov eax,dword ptr [ebp-80h] 00FC08EF cmp dword ptr [ebp+eax*4-44h],1 00FC08F4 jne findMaxPoint+17Ch (0FC090Ch) res++; base[k] = 0; 00FC08F6 mov eax,dword ptr [ebp-18h] 00FC08F9 add eax,1 res++; base[k] = 0; 00FC08FC mov dword ptr [ebp-18h],eax 00FC08FF mov eax,dword ptr [ebp-80h] 00FC0902 mov dword ptr [ebp+eax*4-44h],0 } 00FC090A jmp findMaxPoint+1A8h (0FC0938h) else if(k != 2 and base[k] == 1) { 00FC090C cmp dword ptr [ebp-80h],2 00FC0910 je findMaxPoint+1A8h (0FC0938h) 00FC0912 mov eax,dword ptr [ebp-80h] 00FC0915 cmp dword ptr [ebp+eax*4-44h],1 00FC091A jne findMaxPoint+1A8h (0FC0938h) base[k + 1]++; base[k] = 0; 00FC091C mov eax,dword ptr [ebp-80h] 00FC091F mov ecx,dword ptr [ebp+eax*4-40h] 00FC0923 add ecx,1 00FC0926 mov edx,dword ptr [ebp-80h] 00FC0929 mov dword ptr [ebp+edx*4-40h],ecx 00FC092D mov eax,dword ptr [ebp-80h] 00FC0930 mov dword ptr [ebp+eax*4-44h],0 } } 00FC0938 jmp findMaxPoint+147h (0FC08D7h) } 00FC093A jmp findMaxPoint+12Dh (0FC08BDh) |
#pragma warning (disable : 4996)
#define STRIKE 0
#define HOMERUN 4
#include <cstring>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <tuple>
using namespace std;
int n, ans;
vector<vector<int>> score;
vector<int> seq = { 0,1,2,3,4,5,6,7,8 };
void findMaxPoint() {
do
{ //0번선수가 3번타자가 아닌경우 PASS
if (seq[3] != 0) continue;
//전체 이닝 진행
int nextBatter = 0, res = 0;
for (int i = 0; i < n; ++i) {
int out = 0, base[3] = { 0, };
//한 이닝 진행
int curBatter = nextBatter;
while (out < 3)
{
int curHit = score[i][seq[curBatter]];
if (curHit == STRIKE) {
out++;
}
else {
if (curHit == HOMERUN) {
res++;
if (base[0] == 1) {
base[0] = 0; res++;
}
if (base[1] == 1) {
base[1] = 0; res++;
}
if (base[2] == 1) {
base[2] = 0; res++;
}
}
else { //안타 인 경우
while(curHit--) {
for (int k = 2; k >= 0; --k) {
if (k == 2 and base[k] == 1) {
res++; base[k] = 0;
}
else if (k != 2 and base[k] == 1) {
base[k + 1]++; base[k] = 0;
}
}
}
base[score[i][seq[curBatter]] - 1]++;
}
}
curBatter = (curBatter + 1) % 9; // 타자 순환
}
nextBatter = curBatter; // 3아웃으로 끝. 다음 타자 저장.
}
if (ans < res) ans = res;
} while (next_permutation(seq.begin(),seq.end()));
}
int main()
{
scanf("%d",&n);
for (int i = 0; i < n; ++i) {
vector<int> eachEning;
for (int j = 0; j < 9; ++j) {
int temp;
scanf("%d", &temp);
eachEning.push_back(temp);
}
score.push_back(eachEning);
}
findMaxPoint();
printf("%d", ans);
return 0;
}
2회차
- dfs를 이용함. 의외로 dfs 자체만으로는 next_permutation로 해결했을때와 유의미한 차이가 나지 않았다.
- 오히려 타자의 베이스 위치 계산 알고리즘 개선이 효과가 컸다. bit와 shift연산을 이용함.
- 1회차 330ms -> 2회차 180ms.
- 배열을 순회할때 나머지 연산을 이용하면 코드가 간결하지만, 나머지 연산을 항상 수행해야하므로 많은 반복이 있는 경우엔 속도가 꽤 많이 차이가 났다. 약 40ms.
//curBatter = (curBatter + 1) % 9; //나머지 연산을 항상해야 하므로 속도가 느리다.
if (curBatter == 8) curBatter = 0;
else ++curBatter;
소스코드
#define STRIKE 0
#include <iostream>
#include <vector>
#include <bitset>
using namespace std;
int n, ans;
vector<vector<int>> score;
int seq[9] = { -1,-1,-1,0,-1,-1,-1,-1,-1 };
void findMaxPoint(int num) {
if (num == 9) { // 순서를 모두 뽑은 경우 진행
int curBatter = 0, res = 0;
for (int i = 0; i < n; ++i) {//전체 이닝 진행
int out = 0;
bitset <8> runs;
//한 이닝 진행
while (out < 3)
{
int curHit = score[i][seq[curBatter]];
if (curHit == STRIKE) {
++out;
}
else {
runs[0] = 1;
runs <<= curHit;
res += runs[4] + runs[5] + runs[6] + runs[7];
runs[4] = 0; runs[5] = 0; runs[6] = 0; runs[7] = 0;
}
//curBatter = (curBatter + 1) % 9; //나머지 연산을 항상해야 하므로 속도가 느리다.
if (curBatter == 8) curBatter = 0;
else ++curBatter;
}
//한 이닝 끝
}
ans = ans < res ? res : ans;
return;
}
for (int i = 0; i < 9; ++i) {
if (seq[i] == -1) {
seq[i] = num;
findMaxPoint(num + 1);
seq[i] = -1;
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n;
for (int i = 0; i < n; ++i) {
vector<int> eachEning;
for (int j = 0; j < 9; ++j) {
int temp;
cin >> temp;
eachEning.push_back(temp);
}
score.push_back(eachEning);
}
findMaxPoint(1);
printf("%d", ans);
return 0;
}
'알고리즘 > BOJ(백준)' 카테고리의 다른 글
| [ 백준-17304893번 / 완전탐색 ] 게리맨더링 (삼성 SW) (0) | 2020.04.22 |
|---|---|
| [ 백준-17135번 / 완전탐색 ] 캐슬 디펜스 (삼성SW) (0) | 2020.04.21 |
| [백준-17345165번 / 완전탐색 ] 배열 돌리기 4 (삼성SW) (0) | 2020.04.19 |
| [ 백준-17825번 / 완전 탐색 ] 주사위 윷놀이 (삼성기출) (0) | 2020.04.16 |
| [ 백준-15685번 / 시뮬레이션 ] 드래곤 커브 (삼성SW) (0) | 2020.04.15 |
