Problem 문제풀이
⚾⚾⚾ queue를 사용하고 재사용할 일이 있다면 꼭 비워주어야 한다는
교훈을 알려준 문제이다. 문제 자체는 매우 간단하다. 야구선수 9명의
매 이닝에서 어떤 결과를 얻는지 정해져 있다. 이들의 순서를 어떻게 배치하면
가장 좋은 성적을 얻을 수 있겠는가 simulation하면 되는 문제이다.
시간 복잡도를 잠시 생각해보자. 감독이 1번선수를 마음에 들어해서 4번타자로 정해버렸다.
남은 선수들의 순서를 정하는 경우의 수는 총 8! = 40320이다.
simulation을 할 때 최악의 경우는 이닝당 아웃을 하는 선수가 한 명밖에 없는 경우로
N*27의 simulation을 진행하게 된다. 그럼 최악의 경우 8!*50*27 = 54432000이 걸리지만
1초 안에는 충분히 할 수 있는 연산이다.
cf) 1초가 걸리는 입력의 크기
• O(N):1억
• O(NlgN):5백만
• O(N^2):1만
• O(N^3): 500
• O(2^N): 20
• O(N!): 10
전략
-
N과 M을 기억해보자. 우리는 1~8의 조합을 만들어야한다.
-
선수들의 entry가 정해졌으면 simulation을 시작하자.
-
queue
ground에 현재 주자들의 상황을 나타낼 것이다. -
만약 주자가 있으면 선수의 번호가
-
주자가 없으면 -1이 들어있을 것이다
-
-
simulation을 시작하자.
-
3 out이 됐을 경우 simulation을 끝내고 다음 이닝으로 넘어간다.
이 때 반드시 queue를 비워줘야한다. 필자는 안 비웠다가 30분 헤맸다.
-
-
score의 Max값을 출력한다.
필요한 배열은 총 3가지이다.
-
선수들의 각 이닝별 성적을 저장할 배열
-
선수들의 entry를 저장할 배열
-
entry에 뽑힌 선수인지 확인하는 배열
int used[9];
int order[9];
int ability[50][9];
다음으로 조합이다. N과 M과 거의 비슷하지만 한 가지 다른 점이 있다면
4번째 타자는 1번 선수로 고정되어 있다는 점이다. 이를 고려해서 코드를 작성해보자.
#
used[0] = 1;
order[3] = 0;
void solve(int idx)
{
if (idx == 3)
{
solve(idx + 1);
return;
}
if (idx == 9)
{
simulation();
return;
}
for (int i = 0; i < 9; i++)
{
if (used[i] == 0)
{
order[idx] = i;
used[i] = 1;
solve(idx + 1);
used[i] = 0;
}
}
}
이 정도 했으면 순열과 조합은 껌이다(그렇다고 자만하지는 말자)
이제 simulation을 완성해보자.
void simulation()
{
int lastPlayer = 0;
int outCount = 0;
int score = 0;
queue<int>ground;
for (int i = 0; i < N; i++)
{
while (outCount < 3)
{
int a = ability[i][order[lastPlayer]];
if (a != 0)
{
ground.push(order[lastPlayer]);
for (int j = 0; j < a - 1; j++)
{
ground.push(-1);
}
while (ground.size() > 3)
{
if (ground.front() != -1)
{
score++;
}
ground.pop();
}
}
else
{
outCount++;
}
lastPlayer = (lastPlayer + 1) % 9;
}
while (!ground.empty())
{
ground.pop();
}
outCount = 0;
}
if (answer < score)
{
answer = score;
}
}
이 부분의 구현은 사람마다 다르겠지만 어려운 부분은 전혀 없다.
그러나 queue를 사용했다면 꼭 비워주자. 비우지 않을 경우 재사용할 때 영향을 줘서
오답을 불러온다… 디버깅으로도 파악이 힘들다 ㅠ.ㅠ 전체 코드를 남기며 마무리한다.
#include <iostream>
#include <queue>
using namespace std;
int N, answer;
int used[9];
int order[9];
int ability[50][9];
void simulation();
void solve(int idx);
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
used[0] = 1;
order[3] = 0;
cin >> N;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < 9; j++)
{
cin >> ability[i][j];
}
}
solve(0);
cout << answer;
return 0;
}
void solve(int idx)
{
if (idx == 3)
{
solve(idx + 1);
return;
}
if (idx == 9)
{
simulation();
return;
}
for (int i = 0; i < 9; i++)
{
if (used[i] == 0)
{
order[idx] = i;
used[i] = 1;
solve(idx + 1);
used[i] = 0;
}
}
}
void simulation()
{
int lastPlayer = 0;
int outCount = 0;
int score = 0;
queue<int>ground;
for (int i = 0; i < N; i++)
{
while (outCount < 3)
{
int a = ability[i][order[lastPlayer]];
if (a != 0)
{
ground.push(order[lastPlayer]);
for (int j = 0; j < a - 1; j++)
{
ground.push(-1);
}
while (ground.size() > 3)
{
if (ground.front() != -1)
{
score++;
}
ground.pop();
}
}
else
{
outCount++;
}
lastPlayer = (lastPlayer + 1) % 9;
}
while (!ground.empty())
{
ground.pop();
}
outCount = 0;
}
if (answer < score)
{
answer = score;
}
}