사용자 도구

사이트 도구


ps:problems:boj:6223

Cow Sorting

ps
링크acmicpc.net/…
출처BOJ
문제 번호6223
문제명Cow Sorting
레벨플래티넘 1
분류

그리디

시간복잡도O(n)
인풋사이즈n<=10000
사용한 언어Python
제출기록30864KB / 76ms
최고기록76ms
해결날짜2022/03/02

풀이

코드

"""Solution code for "BOJ 6223. Cow Sorting".

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

Tags: [Greedy]
"""

import sys


def main():
    N = int(sys.stdin.readline())
    grumpiness = [int(sys.stdin.readline()) for x in range(N)]

    min_grumpiness = min(grumpiness)
    orders = sorted(range(N), key=grumpiness.__getitem__)
    is_visited = [False] * N
    answer = 0

    for i in range(N):
        if is_visited[i]:
            continue
        g_vals = []
        cur = i
        while not is_visited[cur]:
            is_visited[cur] = True
            g_vals.append(grumpiness[cur])
            cur = orders[cur]
        answer += min(
            sum(g_vals) + min(g_vals) * (len(g_vals) - 2),
            sum(g_vals) + min(g_vals) + min_grumpiness * (len(g_vals) + 1))

    print(answer)


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
D R​ H A Z
 
ps/problems/boj/6223.txt · 마지막으로 수정됨: 2022/03/04 16:32 저자 teferi