사용자 도구

사이트 도구


ps:problems:boj:3358

Towers of coins

ps
링크acmicpc.net/…
출처BOJ
문제 번호3358
문제명Towers of coins
레벨골드 4
분류

게임 이론

시간복잡도O(n + t)
인풋사이즈n<=100,000, t<=50
사용한 언어Python 3.11
제출기록39068KB / 108ms
최고기록108ms
해결날짜2023/07/08

풀이

  • DP를 이용해서 푸는 가장 기본적인 게임이론 문제
  • DP로 구할때의 시간복잡도는 O(n*m) (n:포지션의 갯수, m:행동의 갯수) 가 되는데, 포지션은 1,000,000 개, 가능한 행동은 3가지이므로 충분히 시간내에 구할수 있다.
  • DP식이 최대 이전 10개 항에 의존하므로, dp테이블은 2^10 크기 이내의 사이클이 존재하게 된다. 사이클을 찾아서 그것을 이용해서 계산하게 되면 시간복잡도를 더 줄일수도 있겠지만 구현 난이도가 너무 높아지므로 생략.
    • 이렇게 풀어야 하는 문제가 9662 이다.

코드

"""Solution code for "BOJ 3358. Towers of coins".

- Problem link: https://www.acmicpc.net/problem/3358
- Solution link: http://www.teferi.net/ps/problems/boj/3358

Tags: [Game theory]
"""


def main():
    # pylint: disable=unused-variable
    K, L, m = [int(x) for x in input().split()]
    N = [int(x) for x in input().split()]

    max_n = max(N)
    is_win_pos = [False] * (max_n + L + 1)
    for i in range(max_n + 1):
        if not is_win_pos[i]:
            is_win_pos[i + 1] = is_win_pos[i + K] = is_win_pos[i + L] = True

    print(''.join('A' if is_win_pos[x] else 'B' for x in N))


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
E W O T G
 
ps/problems/boj/3358.txt · 마지막으로 수정됨: 2023/07/12 14:43 저자 teferi