Problem 문제풀이
배열 사이즈는 4*6*3으로 그렇게 크지 않았다. 이전에 풀었던 N과 M을 참고하여 문제를 풀어보았다.
먼저 main문이다.
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
for (int tc = 0; tc < 4; tc++)
{
int winner_cnt = 0;
int loser_cnt = 0;
int draw_cnt = 0;
answer = 0;
for (int i = 0; i < 6; i++)
{
for (int j = 0; j < 3; j++)
{
cin >> score[i][j];
}
winner_cnt += score[i][0];
draw_cnt += score[i][1];
loser_cnt += score[i][2];
for (int j = 0; j < 6; j++)
{
info[i][j] = -1;
}
}
if(winner_cnt==loser_cnt && draw_cnt%2==0 && winner_cnt+loser_cnt+draw_cnt==30)
{
solve(0, 0);
}
cout << answer << ' ';
}
return 0;
}
이긴 경기의 수는 진 경기의 수와 같아야 하고 비기는 것은 무조건 짝수번 발생한다.
경기는 총 6*5번 이루어지므로 winner_cnt+loser_cnt+draw_cnt==30 이어야 한다.
swea는 출력부에 tc:N 형식의 문제가 많았던 것으로 기억해서 3중 for문으로 만들었다.
이제 solve 함수를 살펴보자. N과 M 포스터를 읽어본 사람이라면 알겠지만
comb 배열에 모든 값이 들어가있지 않으면 마지막 if문을 통과하지 못하고 return하게 된다.
즉, 승/무/패를 정하는 과정에서 모순이 생길 경우 마지막 if문을 통과하지 못한다.
반대로 말하면 마지막 if문에 들어왔다는 것은 모순이 없었다는 의미이다.
이를 토대로 종단조건을 만들어보자.
if (human == 6)
{
answer = 1;
}
Simple is the best.
이제 N과 M을 떠올리며 내가 이기는 경우를 생각해보자.
if (index < score[human][0]) //이길 녀석 정하기
{
for (int i = human+1; i < 6; i++)
{
if (info[human][i] != -1 || info[i][human] != -1 || score[i][2]<=0)
{
continue;
}
info[human][i] = 2;
info[i][human] = 0;
score[i][2]--; //i가 패배한 사람 중 비확정 인원 수
solve(human, index + 1);
info[human][i] = -1;
info[i][human] = -1;
score[i][2]++;
}
}
score에는 나와 상대방과의 전적이 들어있고 초기값으로 -1이 들어있다. 2면 이긴 것이고 1이면 비긴 것 0이면 진 것이다.
내가 i번째 사람을 이겼다면 i번째 사람을 패배시킨 사람 중 한 명이 나로 정해진 것이므로 score[i][2]-=1 해준다.
i번째 사람에게 이길수도 있고 질수도 있다. 따라서 solve를 호출한 뒤 다시 원상 복귀를 시킨다.
비기는 경우와 지는 경우도 마찬가지이다.
else if (index < score[human][0] + score[human][1]) //비길 녀석 정하기
{
for (int i = human + 1; i < 6; i++)
{
if (info[human][i] != -1 || info[i][human] != -1 || score[i][1] <= 0)
{
continue;
}
info[human][i] = 1;
info[i][human] = 1;
score[i][1]--; //i가 비긴 사람 중 비확정 인원 수
solve(human, index + 1);
info[human][i] = -1;
info[i][human] = -1;
score[i][1]++;
}
}
else if (index < score[human][0] + score[human][1] + score[human][2]) //질 녀석 정하기
{
for (int i = human + 1; i < 6; i++)
{
if (info[human][i] != -1 || info[i][human] != -1 || score[i][0] <= 0)
{
continue;
}
info[human][i] = 0;
info[i][human] = 2;
score[i][0]--; //i가 승리한 사람 중 비확정 인원 수
solve(human, index + 1);
info[human][i] = -1;
info[i][human] = -1;
score[i][0]++;
}
}
마지막으로 index가 게임에서 이긴 인원수, 비긴 인원수, 진 인원수와 같아졌을 경우
다음 단계(사람)으로 넘어간다.
else
{
solve(human + 1, 0);
}
모듈화가 중요한 문제였던 것같다. 빠르게 푸는 것보다 정확하게 푸는 것이 중요하다. 1제출 1정답을 목표로!