====== 추 정렬하기 ======

===== 풀이 =====
  * 이 문제와 동일한 문제가 무려 3개나 더 있다. [[ps:problems:boj:2322]], [[ps:problems:boj:2569]], [[ps:problems:boj:6223]]이다.
  * 정렬했을때 각 추가 가야 할 위치들을 구해놓고 보면, 옮겨야 할 추들을 몇개의 사이클들로 분할할 수 있다.
  * 크기 n짜리 사이클을 원래 위치로 돌리기 위해선 n-1번의 스왑이 필요하다. 아무 추 한개를 원래 자리로 옮기는 식으로 스왑하면, n-1번째에는 모두 제자리에 오게된다.
  * 모든 추는 최소 한번씩은 위치를 옮겨야 하는데, 옮길때 항상 가장 무게가 작은 추와 함께 스왑되도록 하는 것이 최적 전략이 된다. 
    * 추의 무게가 2 4 5 3 1 순이라서 5짜리 사이클이 생겼다 치자, 가장 작은 무게인 1이, 5번 자리에 있으니까, 1-5를 스왑하고, 이제 1이 3번 자리에 갔으니 1-3을 스왑, 그리고 1-4, 1-2 순으로 스왑하면 모두 정렬된다.
  * 이때의 총 비용은 sum(X) + min(X) * (len(X)-2) 로 쉽게 구해진다
  * 하지만 이렇게 쉽게 생각하고 구현해서 제출했더니, 틀렸습니다를 받았다
  * 질문 게시판에서 다음의 반례를 찾았다
    * 1 1004 1001 1002 1003 의 경우, 답이 5016이 된다는 것.
  * 저것을 5016으로 만들기 위해서는 1004 1001 1002 1003의 사이클을 n-1 번에 정렬하는 것이 아니라, 1을 사이클의 숫자와 스왑하고, 사이클을 정렬한 다음 다시 1을 사이클 밖으로 옮겨야 한다.
    * 1 1004 1001 1002 1003 를 1001과 1을 스왑해서, 1001 1004 1 1002 1003 으로 바꾸고, 위에서 했던 방법대로 1001 1 1002 1003 1004 형태로 변환한 다음, 마지막에 다시 1001과 1을 스왑하는 것이다. 
  * 이러면 사이클에서 가장 작은 값과 전체에서 가장 작은 값(m)을 먼저 스왑하고, 윗 방법을 쓰고, 다시 스왑을 하니까, 총 비용이 (min(X)+m) + (sum(X)-min(X) + m*(len(X)-1) + (min(X)+m) = sum(X) + min(X) + m*(len(X)+1) 이 된다
  * 이제 이 두 값중에서 작은 값을 고르도록 하면 된다.
  * 시간 복잡도는 O(n).


===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 1851. 추 정렬하기".

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

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:다이아몬드_5}}