문제
N명의 학생들의 성적이 학번순서대로 주어졌다. 학번 구간 [A, B]가 주어졌을 때 이 학생들 성적의 평균을 구하는 프로그램을 작성하라.
입력
첫 번째 줄에 학생 수 N과 구간 수 K가 주어진다. 두 번째 줄에는 학생의 성적 가 주어진다. 번째 줄에는 i번째 구간 가 주어진다.
입력은 다음 조건을 만족한다.
인 정수
인 정수
인 정수
출력
i번째 줄에 i번째 구간의 성적평균(소수셋째자리에서 반올림)을 출력한다.
(차이가 0.01이하이면 정답으로 채점됨)
예시
입력
5 3
10 50 20 70 100
1 3
3 4
1 5
Plain Text
복사
출력
26.67
45.00
50.00
Plain Text
복사
정답
import sys
N, K = list(map(int, sys.stdin.readline().split()))
students = list(map(int, sys.stdin.readline().split()))
# 누적 합 구하기
cum_score = [students[0]]
for i in range(1,N):
cum_score.append(cum_score[i-1]+students[i])
avg_score = []
for _ in range(K):
a, b = list(map(int, sys.stdin.readline().split()))
a -= 1 # 인덱스 맞춤
b -= 1
if a == 0:
avg_score.append(round(cum_score[b]/(b-a+1),2)) # b까지의 누적합 / 학생 수
else:
avg_score.append(round((cum_score[b]-cum_score[a-1])/(b-a+1),2)) # b까지 누적합 - (a-1)까지의 누적합 / 학생 수
for avg in avg_score:
print(avg)
Python
복사
풀이
•
전형적인 구간합 문제이다.
•
누적합을 이용하여 풀면 된다.
•
예를 들어 예시에서 성적들의 누적합 리스트를 구하면 다음과 같다.
10 60 80 150 250
Plain Text
복사
•
이때 1번째 학생부터 3번째 학생까지의 성적합은 누적합 리스트에서 3번째 원소를 가리킨다.
80
Plain Text
복사
•
그리고 3번째 학생부터 4번째 학생까지의 성적합은 누적합 리스트에서 4번째 원소에서 2번째 원소를 뺀 것과 같다.
150-60=90
Plain Text
복사
•
즉, N번째 학생부터 M번째 학생까지의 성적합은 누적합 리스트의 M 번째 원소에서 N-1번째 원소를 뺀 값과 같다. 이때 N=1인 경우 M 번째 원소의 값이 성적합이다.
•
이를 이용해서 코드를 작성하면 다음과 같다.
import sys
N, K = list(map(int, sys.stdin.readline().split()))
students = list(map(int, sys.stdin.readline().split()))
# 누적 합 구하기
cum_score = [students[0]]
for i in range(1,N):
cum_score.append(cum_score[i-1]+students[i])
avg_score = []
for _ in range(K):
a, b = list(map(int, sys.stdin.readline().split()))
a -= 1 # 인덱스 맞춤
b -= 1
if a == 0:
avg_score.append(round(cum_score[b]/(b-a+1),2)) # b까지의 누적합 / 학생 수
else:
avg_score.append(round((cum_score[b]-cum_score[a-1])/(b-a+1),2)) # b까지 누적합 - (a-1)까지의 누적합 / 학생 수
for avg in avg_score:
print(avg)
Python
복사