BOJ/백준-11659-python

문제

풀이

• 내장함수 sum + slicing 으로 처음에 접근하였지만 시간초과로 인해 실패하였다.
• sum은 내부적으로 for문으로 구현하기 때문에 단순 반복문으로 접근하면 안되는 문제였다.
• dp table을 만들어서 누적합을 기록하여 빠르게 접근하였다.

코드

# https://www.acmicpc.net/problem/11659
# boj, 11659: 구간 합 구하기 4, python3
import sys

input = sys.stdin.readline

# 주어진 구간의 누적 합을 반환하는 함수
def solve(d: list, start: int, end: int) -> int:
    # return sum(nums[start-1:end])  # 시간 초과
    return d[end-1] - d[start-1] + nums[start-1]

if __name__ == '__main__':
    n, m = map(int, input().split())  # n: 수의 개수, m: 합을 구해야 하는 횟수
    nums = list(map(int, input().split()))  # nums: 주어진 수 list
    
    d = [0] * n    # dp table 초기화
    d[0] = nums[0]

    for x in range(1, n):  # dp bottom-up
        d[x] = d[x-1] + nums[x]

    for _ in range(m):
        i, j = map(int, input().split())  # i:합을 구해야 하는 구간 시발점 j: 합을 구해야하는 구간 종결점

        print(solve(d, i, j))

결과

출처 & 깃허브

boj 11659
github