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()
ps/problems/boj/3358.txt · 마지막으로 수정됨: 2023/07/12 14:43 저자 teferi
토론