(Python/🥈4)백준 알고리즘 1463번: 1로 만들기

문제 바로가기 

백준 알고리즘 구간 합 구하기 4

 

문제:

수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.

입력:

 

첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.

출력:

총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.

import sys

sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

N, K = map(int,input().split(" "))
lst = list(map(int,(sys.stdin.readline().split(" "))))

for i in range(K):
    left, right = map(int,input().split(" "))
    print(sum(lst[left-1:right]))

처음에 이렇게 했지만 슬라이싱땜에 시간초과가 난다.

dp 에 각 합을 저장해 보고  만약 2,4 이면 4까지의 최댓값 - 2까지의 최댓값을 해주면 된다.

 

import sys

sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

N, K = map(int,input().split(" "))
lst = list(map(int,(sys.stdin.readline().split(" "))))

dp = [0] * (N+1)

for i in range(N):
    dp[i+1] = dp[i] + lst[i]

for i in range(K):
    x, y = map(int,sys.stdin.readline().split(" "))
    print(dp[y] - dp[x-1])

 

이렇게 해주면 된다.

i+1 까지의 최댓값은 이전 최댓값 + 지금 밟기위해 필요한 값이다.

그리고 작은값을 포함해야하므로 dp[x-1] 을 해주도록 한다.