글 읽기 - 리스트 -> 튜플로 바꾸니 시간초과가해결되네요 pypy3에서만..

jmw93 1년 전 0

pypy3 에서만 통과되긴하는데요,

moved_cloud에 원소를 넣을때, 튜플형태로 넣으니 통과가 되긴하네요. 왜 그런지 궁금합니다.

시간복잡도는 array 나, tuple 이나 동일할텐데요,

다들 31번줄에 in 연산자를 쓰는부분에서, 시간초과가 나는것같더라구요

n, m = map(int,input().split())
board = [list(map(int,input().split())) for _ in range(n)]
dy2 = [-1,-1,1,1]
dx2 = [-1,1,-1,1]
dx = [-1,-1,0,1,1,1,0,-1]
dy = [0,-1,-1,-1,0,1,1,1]
clouds = [[n-2,0],[n-2,1],[n-1,0],[n-1,1]]

for _ in range(m):
    direc,dist = map(int,input().split())
    moved_cloud = []
    for y,x in clouds :
        ny = (y+dy[direc-1]*dist) % n
        nx = (x + dx[direc - 1] * dist) % n
        board[ny][nx] += 1
        moved_cloud.append((ny,nx))
    # 물 복사
    for y,x in moved_cloud :
        cnt = 0
        for i in range(4):
            ny = y+dy2[i]
            nx = x+dx2[i]
            if 0<=ny<n and 0<=nx<n and board[ny][nx] > 0 :
                cnt+=1
        board[y][x] += cnt
    # 5번
    new_cloud = []
    for i in range(n):
        for j in range(n):
            if board[i][j] >= 2 and (i,j) not in moved_cloud:
                board[i][j]-=2
                new_cloud.append((i,j))
    clouds = new_cloud

sum = 0
for i in range(n):
    for j in range(n):
        sum+=board[i][j]
print(sum)

sjhkr 1년 전 0

복잡도는 같지만, tuple이 list보다 더 빠릅니다.

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

문제

문제

출처

ICPC

리스트 -> 튜플로 바꾸니 시간초과가해결되네요 pypy3에서만..

jmw93 1년 전 0

sjhkr 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말