랜덤 소트 (1521번) - 백준 (BOJ)

https://www.acmicpc.net/problem/1521

1521번: 랜덤 소트

 

백준 - 랜덤 소트 (1521번)

 

난이도 : Platinum 5

알고리즘 : Dynamic Programming (동적계획법) & Mathematics (Permutation)

풀이 소요 시간 : 검색해서 아이디어 얻음

Time Complexity : O(N! * N^2)

 

from itertools import permutations as p
from itertools import combinations as c


if __name__ == '__main__':
    N = int(input())
    target = tuple(map(int, input().split()))
    mapping = {seq: 0.0 for seq in p(range(1, N+1))}

    for seq in p(range(1, N+1)):
        acc = ways = 0
        for i, j in c(range(N), 2):
            if seq[i] < seq[j]:
                continue

            seq_l = list(seq)
            seq_l[i], seq_l[j] = seq_l[j], seq_l[i]
            acc += mapping[tuple(seq_l)] + 1
            ways += 1
        
        if ways:
            mapping[seq] = acc / ways
        if seq == target:
            break
    
    print(mapping[target])

 

순열의 순서 & 정렬의 특징 & Dynamic Programming,

이 세 가지를 적절히 활용해서 푸는 문제였다.

 

[3, 2, 1] 순열 예시

 

1. 순열의 순서

 

{1, 2, 3} : 이 세 개의 숫자로 만들 수 있는 순열을, 작은 순서대로 나열하면

{1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1} 이 된다.

 

 

2. 정렬의 특징

 

{2, 3, 1}에서 1과 3을 교환해서 {2, 1, 3}을 만든다고 하면,

{2, 1, 3}은 {2, 3, 1}보다 반드시 앞 쪽에 있다.

 

즉, 어떤 수열을 정렬하기 위해 한 쌍의 숫자를 교환하면

그렇게 만들어진 수열은 이전 수열보다 반드시 앞 쪽에 있다.

 

결국 그림으로 그려보면, 낮은 단계로만 향하는 단방향 그래프가 된다.

 

 

3. Dynamic Programming

 

방향이 낮은 쪽으로만 향하는 단방향 그래프이기 때문에,

순열의 순서에서 작은 수열부터 시작해서 DP를 활용할 수 있다.

 

{1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1} 에서

{1, 2, 3} 부터 시작해서, 차례대로 각 수열마다 기대값을 저장하면 된다.

 

(해당 노드의 값) = (자식 노드 값들의 합) / (자식 노드의 개수) 로 저장해두면,

다음 단계 수열들에서 계속 활용할 수 있다.

 

---

스스로 떠올리지 못하고, 검색해서 아이디어를 찾은게 아쉽긴 했지만

순열의 순서와 정렬의 특성을 이용해서 DP로 해결하는

흥미로운 아이디어를 접하고 적용해볼 수 있었다.

 

다음에 비슷한 유형의 문제를 만나게 되면, 그때는 내 힘으로만 풀어봐야겠다.

 

 

---

<References>

https://ps.mjstudio.net/boj-1521

BOJ 1521 - 랜덤 소트