DP2 - 수열의 값을 계산하기

백준 11659

 

import sys

N,M = map(int,sys.stdin.readline().split())

Nlist = [0]+list(map(int,sys.stdin.readline().split()))

for i in range(M) :

    answerlist = list(map(int,sys.stdin.readline().split()))

    sumnum = 0

    for j in range(answerlist[0],answerlist[1]+1) :

        sumnum = sumnum+Nlist[j]

    print(sumnum)

 

N,M이 1000000이 되며, 이로 인해 시간복잡도가 거의 O(100000000000)일 것으로 예상된다. 

이는 당연히 시간제한 1초에게 걸릴 것이다.

 

그래서 풀이를 변경하였다 . 

N,M = map(int,sys.stdin.readline().split())

Nlist = [0]+list(map(int,sys.stdin.readline().split()))

dp = [0] * (N+1)

for i in range(1,N+1) :

    dp[i] = dp[i-1]+Nlist[i]

for j in range(M) :

    start,end= map(int,sys.stdin.readline().split())

    print(dp[end]-dp[start-1])

 

즉, 시간 제한에 걸릴 것 같고 연산을 진행한다면, 그 연산 값을 저장해놓는 dp를 활용하여 시간 복잡도를 줄이는 문제가 있을 수 있다는 것 !

 

백준 2559

import sys

N,K = map(int,sys.stdin.readline().split())

Nlist = list(map(int,sys.stdin.readline().split()))

DP = [0]

for i in range(N) :

    DP.append(sum(Nlist[i:i+K]))

print(max(DP))

 

내가 완성한 코드인데, 답은 충분히 나오고

append로 시간을 좀 줄여보고자 했지만, 그럼에도 시간 초과가 나온다. 

 

import sys

N,K = map(int,sys.stdin.readline().split())

Nlist = list(map(int,sys.stdin.readline().split()))

answer = sum(Nlist[:K]) 

for i in range(N-K) :
    newanswer = sum(Nlist[i:i+K])
    if newanswer> answer:
        answer =newanswer
print(answer)

 

배열 생성을 아예 없애도 마찬가지.. 다른 방안을 찾아봐야 할 것 같다. 

 

<아스키 코드 관련문제로써, 후에 모아서 다시 풀어보도록 하겟다>

 

<답안>

import sys

N,K = map(int,sys.stdin.readline().split())

Nlist = list(map(int,sys.stdin.readline().split()))

partsum= sum(Nlist[:K])

answerlist = [partsum]

for i in range(N-K) :

    partsum = partsum - Nlist[i]+Nlist[i+K]

    answerlist.append(partsum)

   

print(max(answerlist))

sum을 계속해서 구할 필요 없다는 것이 장점이었다. 

Sum후 slice 배열을 추가하여도, 시간 복잡도가 O(N)이기 떄문에 지양해야함을 깨달았다. 

 

백준 16139

import sys

S = sys.stdin.readline().strip()

#입력받는 문자열임

Q = int(sys.stdin.readline())

for i in range(Q) :

 a,lin,rin = sys.stdin.readline().split()

 l = int(lin)

 r = int(rin)

 sum = 0

 for j in range(l,r+1) :

     if S[j] == a :

         sum += 1

 print(sum)

 50점 짜리 풀이. 

 시간 복잡도가 굉장히 클 것 같지만, 50점을 어떻게 받는지 풀어보고 싶어서 이렇게 풀어보았다.

 

#100점풀이를 보니, 아스키코드를 활용하는 것 같다. 이는 정리해서 다시 올리도록 하겠다. 

 

백준 11660

import sys

N,M = map(int,sys.stdin.readline().split())

Nlist= []
for i in range (N) :
    inputlist = list(map(int,sys.stdin.readline().split()))
    Nlist.append(inputlist)

dp = [ [0]*(N+1) for _ in range(N+1) ]

for i in range(1, N+1 ) :
    for j in range(1,N+1) :
        dp[i][j] = dp[i-1][j]+dp[i][j-1] + Nlist[i-1][j-1] - dp[i-1][j-1]


for i in range(M) :

    x1,y1,x2,y2 = map(int,sys.stdin.readline().split())

    print(dp[x2][y2] -dp[x2][y1-1] -dp[x1-1][y2] + dp[x1-1][y1-1])

 

. 부분합을 쓰지 않았을때 , 시간초과 가 났다.

 

도형적인 측면을 활용해 풀어냈다.