글 읽기 - 어디가 틀렸는지 알려주시면 감사하겠습니다

lovemay28s 3년 전 0

heap을 이 문제 풀면서 처음 알아서 모듈 안쓰고 코드 짜봤는데 어디가 틀렸는지 모르겠네요

질문글에 있는 반례는 다 해봤습니다

import sys
n = int(sys.stdin.readline())
l = []
sum = 0

for i in range(n):
    l.append(int(sys.stdin.readline()))

l.sort()


def heapify(list, index, n):
    s_index = index
    if index*2+1 <= n-1 and list[index] > list[index*2+1]:
        index = index*2+1
    if index*2+2 <= n-1 and list[index] > list[index*2+2]:
        index = index*2+2
    if s_index != index:
        list[s_index], list[index] = list[index], list[s_index]
        heapify(list, index, n)


while True:
    k = len(l)
    if k == 1:
        break
    elif k == 2:
        sum += l[0] + l[1]
        break
    elif l[1] < l[2]:
        l[1] = l[0]+l[1]
        sum += l[1]
        heapify(l, 1, k)
    else:
        l[2] = l[0]+l[2]
        sum += l[2]
        heapify(l, 2, k)
    l[0] = l.pop()
    heapify(l, 0, len(l))

print(sum)

pmn0001 3년 전 1

heapify 함수에서 실수가 있으셨네요

def heapify(list, index, n):
    s_index = index
    if s_index*2+1 <= n-1 and list[index] > list[s_index*2+1]:
        index = s_index*2+1
    if s_index*2+2 <= n-1 and list[index] > list[s_index*2+2]:
        index = s_index*2+2
    if s_index != index:
        list[s_index], list[index] = list[index], list[s_index]
        heapify(list, index, n)

lovemay28s 3년 전 0

이해했습니다 감사합니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

어디가 틀렸는지 알려주시면 감사하겠습니다

lovemay28s 3년 전 0

pmn0001 3년 전 1

lovemay28s 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말