사용자 도구

사이트 도구


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()

토론

댓글을 입력하세요:
N S V S N
 
ps/problems/boj/31027.txt · 마지막으로 수정됨: 2025/08/21 05:09 저자 teferi