[실버 III] 17390번. 이건 꼭 풀어야 해!

 문제 

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

17390번: 이건 꼭 풀어야 해!

 사용 언어 

Python3

 풀이 과정 

나는 처음에 이 문제의 설명을 이해하기가 너무 어려웠다... 대체 왜 설명을 저렇게밖에 못했는지 의문이다.

일단 비내림차순으로 정렬한다길래 내림차순이 아닌 수열중에 랜덤을 말하는건가? 했는데 정렬이라는 말이 있어서 결국 오름차순으로 정렬한다는 말이었다.

그리고 다음 설명도 헷갈렸는데 결국 오름차순한 수열의 L번째 인덱스부터 R번째 인덱스의 합을 의미하는 것이었다.

 

따라서 처음에는 다음과 같이 코드를 짰는데 시간 초과가 났다.

from sys import stdin
input = stdin.readline

N, Q = map(int, input().split())
array = list(map(int, input().split()))
array.sort()
for i in range(Q):
    L, R = map(int, input().split())
    print(sum(array[L-1:R]))

짜면서도 슬라이싱과 sum 함수가 여러 번 실행되겠다 싶긴 했는데 시간 초과가 나서... 다른 방법이 필요했다.

이 문제의 알고리즘이 '누적합'이었기 때문에 개념을 찾아보고 dp의 메모이제이션 하듯이 prefix_sum이라는 함수를 만들어줘서 풀었다. 시간은 좀 걸렸지만 결국 맞았습니다!!

 

 제출 답안 

from sys import stdin
input = stdin.readline

N, Q = map(int, input().split())
array = list(map(int, input().split()))
array.sort()    
prefix_sum = [0]
for i in range(N):
    prefix_sum.append(prefix_sum[i] + array[i])
 
for _ in range(Q):
    L, R = map(int,input().split())
    print(prefix_sum[R] - prefix_sum[L-1])

 

 다른 사람 코드 

1. 없는 게 없는(?) 파이썬에는 누적합 자료형도 있었다! accumulate를 import하여 푼 코드이다.

from itertools import accumulate
input = __import__('sys').stdin.readline
 
n, q = map(int, input().split())
a = sorted([*map(int, input().split())])
p_sum = list(accumulate(a))
p_sum.insert(0, 0)
 
for _ in range(q):
    l, r = map(int, input().split())
    l -= 1
    print(p_sum[r] - p_sum[l])

출처 : https://kau-algorithm.tistory.com/502

➡ 아무래도 파이썬은 관련 라이브러리를 적극 사용하는 게 최적화에 도움이 되기 때문에 내가 푼 것보다 시간이 짧은 걸 확인했다.