[ BOJ 11659 ] 구간 합 구하기4(Python)

uoayop·2021년 6월 1일
0

알고리즘 문제

목록 보기
81/103
post-thumbnail

문제

https://www.acmicpc.net/problem/11659

구간 합(prefix sum) 개념 익히는 문제!
약간 dp 느낌~~


문제 풀이

0. 입력 받기

n, m = map(int,input().rsplit())
nums = list(map(int,input().rsplit()))

1. prefix 배열 정의하기

prefix = [0]
curr = 0

for n in nums:
    curr += n
    prefix.append(curr)

prefix[i] = i번째 인덱스까지의 합

2. 출력하기

for _ in range(m):
    i, j = map(int,input().rsplit())
    print(prefix[j]-prefix[i-1])

[i~j] 범위의 수를 모두 더한 값
= [j] 까지 모두 더한 값 - [i-1] 까지 모두 더한 값


코드

import sys
input = sys.stdin.readline

n, m = map(int,input().rsplit())
nums = list(map(int,input().rsplit()))
prefix = [0]
curr = 0

for n in nums:
    curr += n
    prefix.append(curr)

for _ in range(m):
    i, j = map(int,input().rsplit())
    print(prefix[j]-prefix[i-1])
profile
slow and steady wins the race 🐢

0개의 댓글