https://www.acmicpc.net/problem/20923
20923번: 숫자 할리갈리 게임
첫째 줄에는 도도와 수연이가 가지는 카드의 개수 $N$($ 1 \leq N \leq 30\,000$)과 게임 진행 횟수 $M$($ 1 \leq M \leq 2\,500\,000$)이 주어진다. 둘째 줄부터 $N$개의 줄에는 띄어쓰기로 구분하여 도도와 수연
www.acmicpc.net
처음에 문제가 이해가 안되서 한참 보다가 질문에서 두 사람이 낸 카드의 총합이 M이라는 걸 보고 아.. 그제야 이해했다.
이해한 후에는 그렇게 어렵지 않았는데, 처음에 바보같이 그라운드의 카드를 종을 친 사람의 덱으로 가져올 때 그라운드를 스택이라고 생각하고 풀어서 시간초과가 났다. 아니 사실 pypy로 돌렸을 땐 틀렸습니다. 라고 나왔는데 그건 왜 그런 건지 모르겠다..
그라운드도 덱으로 구현한 후에는 pypy3로 통과했다. python은 여전히 시간초과다,,ㅎㅎ
import sys
from collections import deque
input = sys.stdin.readline
N, M = map(int, input().split())
do = deque()
su = deque()
for _ in range(N):
a, b = map(int, input().split())
do.append(a)
su.append(b)
groundDo = deque()
groundSu = deque()
def get(a,b,deque):
while (b):
deque.appendleft(b.popleft())
while (a):
deque.appendleft(a.popleft())
def solve():
v1 = 0
v2 = 0
if groundDo:
v1 = groundDo[-1]
if groundSu:
v2 = groundSu[-1]
if (v1==5 or v2==5):
get(groundDo, groundSu, do)
elif (v1+v2 == 5):
get(groundSu, groundDo, su)
return
for i in range(M):
if (i%2==0):
groundDo.append(do.pop())
if (len(do)==0):
break
solve()
else:
groundSu.append(su.pop())
if (len(su)==0):
break
solve()
if (len(do) > len(su)):
print('do')
elif (len(do) < len(su)):
print('su')
else:
print('dosu')
'알고리즘💻 > 스택&큐&덱' 카테고리의 다른 글
BOJ 2812번: 크게 만들기 (0) | 2021.07.24 |
---|---|
BOJ 9012번: 괄호 (0) | 2021.07.24 |
BOJ 18115번: 카드 놓기 (0) | 2021.07.22 |
BOJ 3078번: 좋은 친구 (0) | 2021.07.22 |
BOJ 2304번: 창고 다각형 (0) | 2021.07.22 |