💡문제
작곡가인 GUN은 박자의 빠르기가 변화하는 곡을 쓰는 걸 좋아한다.
혼신의 힘을 다해 곡을 완성한 GUN은 자기가 쓴 곡의 초당 박자 변화량의 합이 얼마나 되는지 궁금해졌다. 하지만 GUN의 노래는 박자가 변화하는 곳이 많아 구간의 변화량 합을 일일이 계산하기 어렵다. GUN은 당신에게 이 곡의 특정 부분들의 구간별 초당 박자 변화량의 합을 구해달라고 요청했다. GUN을 도와 주어진 구간들의 초당 박자 변화량의 합을 구해주자.
단, i 초와 j 초 구간 사이의 초당 박자 변화량의 합은 
라고 정의하고 j-1 < i 인 경우엔
이다.
그리고 기호 |a|는 임의의 실수 a에 대해 a<0 이면 |a| = -a 이고 a≥0 이면 |a| = a임을 나타내는 기호이다.
입력
입력의 첫 번째 줄에는 GUN이 쓴 노래의 길이 N(1 ≤ N ≤ 1,000) 초와 초당 박자 변화량의 합을 구해야 하는 구간의 수 Q(1 ≤ Q ≤ 1,000)이 공백으로 구분되어 주어진다.
입력의 두 번째 줄에는 순서대로 GUN이 쓴 노래의 박자 빠르기를 나타내는 수열 a1 a2, ... , an 이 공백으로 구분되어 주어지며, ai (-104 ≤ ai ≤ 104)는 i 초일 때 박자의 빠르기라고 한다.
입력의 세 번째 줄부터 Q 줄에 걸쳐 변화량의 합을 구해야 하는 구간의 시작점과 끝점 Q(i,l), Q(i,r) (1 ≤ Q(i,l) ≤ Q(i,r) ≤ N)가 주어진다.
출력
GUN이 쓴 곡의 구간의 초당 박자 변화량의 합을 입력 순서대로 Q 줄에 걸쳐 출력한다.
예제입력
4 3
100 101 382 573
1 1
1 3
2 4예제출력
0
282
472📖내가 작성한 Code
import sys
'''
구간합인가?
'''
def make_prefix_sum(n, array):
prefix_sum = [0]*(n+1)
start = array[0]
for i in range(1, n):
prefix_sum[i] = prefix_sum[i-1] + abs(array[i] - start)
start = array[i]
return prefix_sum
def find_change(prefix_sum, array):
result = []
for start, end in array:
result.append(prefix_sum[end-1] - prefix_sum[start-1])
return result
def main():
inputs = map(int, sys.stdin.read().split())
n, q = next(inputs), next(inputs)
prefix_sum = make_prefix_sum(n, [next(inputs) for _ in range(n)])
sys.stdout.write('\n'.join(map(str, find_change(prefix_sum, [(next(inputs), next(inputs)) for _ in range(q)]))))
if __name__ == '__main__':
main()
✍️풀이과정
이제 딱보면 누적합 보임! 근데 N이 1000개라서 이중 반복문 돌려도 안터질듯.
달달한 5등
🧠 코드 리뷰
- 불필요한 변수 사용 : 프리픽스 합을 계산할 때, start 변수를 따로 관리하기보다는 이전 원소를 직접 참조하는 방법이 더 직관적입니다.
프리픽스 배열의 크기를 n+1로 할당했지만 실제로는 0부터 n-1까지만 사용되고 있습니다. 이로 인해 약간의 혼동이 있을 수 있습니다.
🛠️AI 개선 코드
import sys
def compute_prefix_sum(n, values):
"""
연속된 구간의 절대값 차의 누적합을 계산합니다.
prefix[i] = |values[1]-values[0]| + |values[2]-values[1]| + ... + |values[i]-values[i-1]|
단, 0번 인덱스는 0으로 설정합니다.
"""
prefix = [0] * n # prefix[0]은 항상 0
for i in range(1, n):
prefix[i] = prefix[i - 1] + abs(values[i] - values[i - 1])
return prefix
def process_queries(prefix, queries):
"""
1-indexed 쿼리 (start, end)를 입력받아 각 구간의 누적 차이 합을 계산합니다.
계산식: prefix[end - 1] - prefix[start - 1]
"""
return [prefix[end - 1] - prefix[start - 1] for start, end in queries]
def main():
data = list(map(int, sys.stdin.read().split()))
it = iter(data)
n = next(it)
q = next(it)
values = [next(it) for _ in range(n)]
prefix = compute_prefix_sum(n, values)
queries = [(next(it), next(it)) for _ in range(q)]
results = process_queries(prefix, queries)
sys.stdout.write('\n'.join(map(str, results)))
if __name__ == '__main__':
main()
💻결과
🖱️참고 링크
