테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.

====== 문제제목 ======

===== 풀이 =====
  * [[ps:problems:boj:1851]], [[ps:problems:boj:2322]], [[ps:problems:boj:2569]], [[ps:problems:boj:6223]]이 모두 동일한 문제이다. 풀이는 [[ps:problems:boj:1851]]을 참고.

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 2569. 짐정리".

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

Tags: [Greedy]
"""

import sys


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

    min_w = min(w)
    orders = sorted(range(n), key=w.__getitem__)
    is_visited = [False] * n
    answer = 0

    for i in range(n):
        if is_visited[i]:
            continue
        weights = []
        cur = i
        while not is_visited[cur]:
            is_visited[cur] = True
            weights.append(w[cur])
            cur = orders[cur]
        answer += min(
            sum(weights) + min(weights) * (len(weights) - 2),
            sum(weights) + min(weights) + min_w * (len(weights) + 1))
    print(answer)


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:플래티넘_1}}