ps:problems:boj:15460
My Cow Ate My Homework
ps | |
---|---|
링크 | acmicpc.net/… |
출처 | BOJ |
문제 번호 | 15460 |
문제명 | My Cow Ate My Homework |
레벨 | 실버 2 |
시간복잡도 | O(n) |
인풋사이즈 | n<=100,000 |
사용한 언어 | Python 3.11 |
제출기록 | 41316KB / 108ms |
최고기록 | 108ms |
해결날짜 | 2023/07/24 |
풀이
- K개를 먹었을 때의 점수는, 뒤쪽의 N-K개에 대해서 ({총합} -{최솟값}) / (N-K) 로 구하면 된다. 뒤에서부터 이터레이션 하면서 총합과 최솟값을 갱신하면 된다. 시간복잡도는 O(N)
- 출력해야 하는 값이 최대 점수가 아니라, 최대 점수를 만들수 있는 모든 K라는 것에 주의. K의 범위가 [1,N-2] 라는 것도 실수하기 쉽다.
코드
"""Solution code for "BOJ 15460. My Cow Ate My Homework".
- Problem link: https://www.acmicpc.net/problem/15460
- Solution link: http://www.teferi.net/ps/problems/boj/15460
"""
INF = float('inf')
def main():
N = int(input())
scores = [int(x) for x in input().split()]
lowest = total = scores[-1]
score_by_k = [-INF] * N
for count, score in enumerate(scores[-2:0:-1], start=2):
lowest = min(lowest, score)
total += score
score_by_k[N - count] = (total - lowest) / (count - 1)
max_score = max(score_by_k)
print(*(k for k, score in enumerate(score_by_k) if score == max_score))
if __name__ == '__main__':
main()
ps/problems/boj/15460.txt · 마지막으로 수정됨: 2023/07/24 15:57 저자 teferi
토론