사용자 도구

사이트 도구


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()

토론

댓글을 입력하세요:
U P W M G
 
ps/problems/boj/15460.txt · 마지막으로 수정됨: 2023/07/24 15:57 저자 teferi