글 읽기 - 8911 거북이 시간초과 관련 질문(Python)

purpose 3년 전 0

시간초과가 발생합니다.

다른 분들의 솔루션을 확인한 결과 전개 상 비슷한 것 같은데 왜 정답이 나오지 않는지 궁금합니다.

제한시간 1초에 문자 500개라 충분히 시간복잡도를 충족한다고 생각하는데 왜 시간초과가 발생하는지 모르겠습니다. 코드 한번 봐주시면 감사하겠습니다!

import sys
# input = sys.stdin.readline

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

n = int(input().rstrip())
for _ in range(n):
    box = [[0]*1001 for _ in range(1001)]
    
    di = 0 # 위를 바라보고 있다.
    X, Y = 500, 500 # 현재 위치
    box[500][500] = 1
    string = input().rstrip()
    
    maxX = 500
    minX = 500
    maxY = 500
    minY = 500
    
    for ch in string:
        if ch == 'F':
            X += dx[di]
            Y += dy[di]
            box[X][Y] = 1
        elif ch == 'B':
            X -= dx[di]
            Y -= dy[di]
            box[X][Y] = 1
        elif ch == 'R':
            di += 1
            di %= 4
        elif ch == 'L':
            di -= 1
            di %= 4
        maxX = max(X, maxX)
        maxY = max(Y, maxY)
        minX = min(X, minX)
        minY = min(Y, minY)
        
    print((maxX-minX)*(maxY-minY))
    

ehdrmsl2001 3년 전 1

box만 빼니까 통과하네요..

import sys
input = sys.stdin.readline

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

n = int(input().rstrip())
for _ in range(n):
    
    di = 0 # 위를 바라보고 있다.
    X, Y = 500, 500 # 현재 위치
    string = input().rstrip()
    
    maxX = 500
    minX = 500
    maxY = 500
    minY = 500
    
    for ch in string:
        if ch == 'F':
            X += dx[di]
            Y += dy[di]
        elif ch == 'B':
            X -= dx[di]
            Y -= dy[di]
        elif ch == 'R':
            di += 1
            di %= 4
        elif ch == 'L':
            di -= 1
            di %= 4
        maxX = max(X, maxX)
        maxY = max(Y, maxY)
        minX = min(X, minX)
        minY = min(Y, minY)
        
    print((maxX-minX)*(maxY-minY))
    

purpose 3년 전 0

ehdrmsl2001

감사합니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

8911 거북이 시간초과 관련 질문(Python)

purpose 3년 전 0

ehdrmsl2001 3년 전 1

purpose 3년 전 0

ehdrmsl2001

감사합니다.

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말