글 읽기 - 파이썬으로 푸는데......O(n^2)인거 같은데 이거 더 짧아야하나요??

blutics 6년 전 0

dp로 풀려는데 전체 공간을 할당하려니가 메모리초과가 나서

값이 나오는데로 바로바로 s에 더해주는 식으로 짰습니다.

시간초과때문에 pypy3로 한번 돌려봤는데

런타임에러가 나더라구요. 일단 개수가 적은 케이스에서

답은 잘 나오는거 같은데 말이죠....

조언 부탁드립니다.

n=int(input())
y=[*map(int,input().split())]
s=0
z=[]
s+=sum(y)
for i in range(1,len(y)):
    w=[]
    for j in range(i-1):
        w+=y[i]^z[j],
        s+=w[-1]
    w+=y[i]^y[i-1],
    s+=w[-1]
    z=w
print(s)

h0ngjun7 6년 전 1

O(N log 10억)에 풀어야 합니다.

blutics 6년 전 0

감사합니다.

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

문제

문제

출처

ICPC

파이썬으로 푸는데......O(n^2)인거 같은데 이거 더 짧아야하나요??

blutics 6년 전 0

h0ngjun7 6년 전 1

blutics 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말