ps:problems:boj:31027
물고기 게임
ps | |
---|---|
링크 | acmicpc.net/… |
출처 | BOJ |
문제 번호 | 31027 |
문제명 | 물고기 게임 |
레벨 | 플래티넘 5 |
분류 |
게임 이론 |
시간복잡도 | O(n) |
인풋사이즈 | n<=500000 |
사용한 언어 | Python 3.13 |
제출기록 | 106684KB / 256ms |
최고기록 | 256ms |
해결날짜 | 2025/08/21 |
풀이
- 다양한 전략이 존재할 것처럼 보이지만, 중간지점까지 가기 전에 방향을 꺾는 것은 중간지점까지 간 이후에 꺾는 것보다 언제나 하위호환이기 때문에, 실질적으로 유효한 전략은 몇 개 되지 않는다. 내가 전략을 선택했을 때, 다시 그 다음에 상대가 선택할 수 있는 전략을 고려하고, 미니맥스 방식으로 스코어를 계산해주면 된다.
- 구체적인 방법은 에디토리얼 참고.
- 시간복잡도는 O(n)
코드
"""Solution code for "BOJ 31027. 물고기 게임".
- Problem link: https://www.acmicpc.net/problem/31027
- Solution link: http://www.teferi.net/ps/problems/boj/31027
Tags: [game theory]
"""
def main():
N = int(input())
A1 = [int(x) for x in input().split()]
A2 = [int(x) for x in input().split()]
if N % 2 == 1:
score1 = sum(A1[: N // 2]) + sum(A2[: N // 2])
score2 = min(sum(A1), score1 + A1[N // 2] + A2[N // 2])
otto_score = max(score1, score2)
else:
score1 = sum(A1[: N // 2]) + sum(A2[: N // 2])
score2a = max(score1, sum(A1))
score2b = score1 + A1[N // 2] + A2[N // 2]
score2 = min(score2a, score2b)
otto_score = max(score1, score2)
print(otto_score, sum(A1) + sum(A2) - otto_score)
if __name__ == '__main__':
main()
ps/problems/boj/31027.txt · 마지막으로 수정됨: 2025/08/21 05:09 저자 teferi
토론