글 읽기 - 시간초과가 나옴니다

andrewpark05 2년 전 0

시간초과가 나오는데 어디때문인지 도와주세요

task=input().split()
a=int(task[0])
b=int(task[1])
d=int(task[2])
N=int(task[3])
A=[]
B=[]
for i in range(N+1):
    if i==0:
        A.append(1)
    elif i<a:
        A.append(0)
    elif i<b:
        x=0
        for j in range(len(A)-a+1):
            x+=A[j]
        A.append(x)
    elif i<d:
        x=0
        for j in range(b-a):
            x+=A[i+j-b+1]
        A.append(x)
    else:
        N-=i
        break
for i in range(N+1):
    B[:]=A[:]
    x=0
    for j in range(b-a):
        x+=B[j+d-b+1]
    for i in range(len(B)-1):
        A[i]=B[i+1]
    A[len(B)-1]=x
cal=0
for i in A:
    cal+=i
print(cal%1000)

ai4youej 2년 전 0

빠른 입출력을 사용해보세요

sonjaewon 2년 전 0

입출력이 5개밖에 없어서 입출력의 문제는 아닌 것 같습니다.

sonjaewon 2년 전 2

``B[:]=A[:]``

여기서 복사가 일어나기 때문에 느린 것 같습니다.

(설명) A 배열 최대 길이 N, B 배열 최대 길이 N, 복사 N 번 : O(N^2)

andrewpark05 2년 전 0

어떻게 바꾸어야하나요?

약간만 더 도와주세요...

djm03178 2년 전 1

이전부터 계속 시간초가라고 쓰시는 걸 여러 번 봐서 한 번 말씀드리는데, 가가 아니라 과입니다. 어떤 기준을 넘어섰음을 의미하는 그 초과입니다.

andrewpark05 2년 전 0

코드를 보다보니까 그 부분이 필요가 없는것 같아서 없엤습니다만 아직도 시간초과가 나오네요

task=input().split()
a=int(task[0])
b=int(task[1])
d=int(task[2])
N=int(task[3])
A=[]
B=[]
for i in range(N+1):
    if i==0:
        A.append(1)
    elif i<a:
        A.append(0)
    elif i<b:
        x=0
        for j in range(len(A)-a+1):
            x+=A[j]
        A.append(x)
    elif i<d:
        x=0
        for j in range(b-a):
            x+=A[i+j-b+1]
        A.append(x)
    else:
        N-=i
        break
for i in range(N+1):
    x=0
    for j in range(b-a):
        x+=A[j+d-b+1]
    for i in range(len(A)-1):
        A[i]=A[i+1]
    A[len(A)-1]=x
cal=0
for i in A:
    cal+=i
print(cal%1000)

sonjaewon 2년 전 0

중첩 for 때문에 오래 걸리는 것 같습니다.

andrewpark05 2년 전 0

아에 다른 방법으로 풀어서 되었습니다

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

문제

문제

출처

ICPC

시간초과가 나옴니다

andrewpark05 2년 전 0

ai4youej 2년 전 0

sonjaewon 2년 전 0

sonjaewon 2년 전 2

andrewpark05 2년 전 0

djm03178 2년 전 1

andrewpark05 2년 전 0

sonjaewon 2년 전 0

andrewpark05 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말