34009번 - Bob부 멍충이
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 512 MB | 886 | 449 | 386 | 52.022% |
문제
Alice와 Bob이 길이가 $N$인 서로 다른 양의 정수로 이루어진 수열 $A_1, A_2, \cdots , A_N$에서 게임을 진행한다. 현재 수열에 남은 원소의 개수가 짝수라면, Alice의 점수가 $A_1$만큼 증가하고, 홀수라면 Bob의 점수가 $A_1$만큼 증가한다. 이후 수열에서 $A_1$은 제거된다. 수열이 비게 되면 게임이 종료된다.
게임을 시작하기 전을 제외한 모든 순간에 Alice의 점수가 Bob의 점수보다 크다면 Alice가 이긴다. 그렇지 않은 순간이 한 번이라도 존재하면 Bob이 이긴다. 이때, 배열을 적절하게 섞어서 Alice가 이길 수 있는지 알아보자.
입력
첫째 줄에 수열 $A$의 크기 $N$이 주어진다. $(1 \le N \le 10^5)$
둘째 줄에 $A_1, A_2, \cdots , A_N$이 공백으로 구분되어 주어진다. $(1 \le A_i \le 10^9)$
$A_i$는 서로 다르며, 입력으로 주어지는 모든 수는 정수이다.
출력
Alice가 이길 수 있도록 배열을 섞을 수 있는 경우 Alice를, 그렇지 않은 경우 Bob을 출력한다.
예제 입력 1
4 1 2 3 4
예제 출력 1
Alice
예제 $1$의 경우 수열을 $4, 3, 2, 1$로 배열할 경우 Alice와 Bob은 아래 표와 같이 점수를 얻는다.
| 수열 | Alice | Bob |
| $4, 3, 2, 1$ | $+4$ | |
| $3, 2, 1$ | $+3$ | |
| $2, 1$ | $+2$ | |
| $1$ | $+1$ |
출처
University > 성균관대학교 > 2025 SKKU 프로그래밍 대회 A번