https://www.acmicpc.net/problem/20364
코드
from collections import deque
import sys
input = sys.stdin.readline
n, q = map(int, input().split())
dp = [-1]*(n+1) # dp[i]는 1번에서 i번까지 가는 길에 가장 처음 마주치는 점유된 땅 번호
for i in range(q):
want = int(input())
if dp[want] == -1: # 가는 길에 이미 점유된 땅이 없음
# 이 땅 아래로는 다 이 땅을 지나야만 한다고 표시
q = deque([want])
while q:
now = q.popleft()
dp[now] = want
for nx in [now*2, now*2+1]:
if nx <= n:
q.append(nx)
print(0)
else: # 가는 길에 점유된 땅이 있음
print(dp[want])
처음에는 원하는 땅에서부터 1번 노드까지 거슬러 올라가며 이미 점유된 땅이 있는지 확인하는 방식으로 했는데, 시간 초과가 발생해서 위와 같은 방식으로 바꿨다. 근데도 시간 초과가 발생해서 확인해보니 입력 방법을 `sys.stdin.readline`으로 바꿔주지 않으면 파이썬은 시간 초과가 발생하는 것 같다.
주어진 입력 값들의 범위가 2 ≤ N < 220, 1 ≤ Q ≤ 200,000이니까 입력 시간을 줄였어야 하는데 신경쓰지 못한 실수...아마 입력 방법을 이렇게 바꿔주면 처음에 생각한 방법으로도 가능한 것 같다.
'문제풀이 > DP' 카테고리의 다른 글
[Python/파이썬] 백준 10164번 격자상의 경로 (0) | 2024.06.25 |
---|---|
[Python/파이썬] 백준 17212번 달나라 토끼를 위한 구매대금 지불 도우미 (0) | 2024.06.22 |
[Python/파이썬] 백준 5569번 출근 경로 (0) | 2024.05.26 |
[Python/파이썬] 백준 15990번 1, 2, 3 더하기 5 (0) | 2024.05.23 |
[Python/파이썬] 백준 4097번 수익 (1) | 2024.05.15 |