사용자 도구

사이트 도구


ps:problems:boj:20366

같이 눈사람 만들래?

ps
링크acmicpc.net/…
출처BOJ
문제 번호20366
문제명같이 눈사람 만들래?
레벨골드 3
시간복잡도O(n^2logn)
인풋사이즈n<=600
사용한 언어Python
제출기록93896KB / 536ms
최고기록424ms
해결날짜2022/04/05

풀이

  • 네개의 수의 합/차가 조건을 만족하는 수를 찾는 문제.
  • 기본적으로는 수집합 과도 같은 테크닉이다. 모든 페어의 대한 합을 저장해놓고, 이들을 갖고 계산하는 방식으로 시간 복잡도를 O(n^4)가 아닌 O(n^2)로 줄인다.
  • 구해놓은 합들 중에서, 차이가 가장 적은 값들을 찾기 위해서는, 합들을 모두 정렬한 뒤에 인접한 것끼리 비교하면 된다. n^2개의 값들을 정렬해야 하므로 정렬에 O(n^2logn)이 되고, 비교하는 것은 O(n^2)에 처리된다.

코드

"""Solution code for "BOJ 20366. 같이 눈사람 만들래?".

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

import itertools


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

    snowmans = []
    for i, h_i in enumerate(H):
        snowmans.extend((h_i + h_j, {i, j}) for j, h_j in enumerate(H[:i]))
    answer = min(
        (h2 - h1)
        for (h1, ind1), (h2, ind2) in itertools.pairwise(sorted(snowmans))
        if not (ind1 & ind2))
    print(answer)


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
F K O T J
 
ps/problems/boj/20366.txt · 마지막으로 수정됨: 2022/05/13 12:42 저자 teferi