사용자 도구

사이트 도구


ps:problems:boj:18310

안테나

ps
링크acmicpc.net/…
출처BOJ
문제 번호18310
문제명안테나
레벨실버 3
분류

절댓값 함수의 최솟값

시간복잡도O(nlogn)
인풋사이즈n<=200,000
사용한 언어Python 3.11
제출기록53652KB / 140ms
최고기록108ms
해결날짜2024/11/25

풀이

  • 가장 기본적인 형태의 절댓값 함수의 최솟값 문제. 모든 좌표값 중에서 중앙값이 최적 위치가 된다.
  • 좌표값을 정렬해서 중앙값을 찾으면 되므로 시간복잡도는 O(nlogn)

코드

"""Solution code for "BOJ 18310. 안테나".

- Problem link: https://www.acmicpc.net/problem/18310
- Solution link: http://www.teferi.net/ps/problems/boj/18310
"""

from teflib import convexopt


def main():
    N = int(input())  # pylint: disable=unused-variable
    poses = [int(x) for x in input().split()]

    _, answer = convexopt.min_sum_of_abs_funcs(poses, also_return_argmin=True)
    print(answer)


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
F I X O I
 
ps/problems/boj/18310.txt · 마지막으로 수정됨: 2024/11/25 07:29 저자 teferi