[일반] 정렬 비용을 최소화하는 방법이 뭔가요

[익명(219.255)]

중복값이 가능한 무작위배열 A(ex. 74335) 에서 정렬된 배열(33457)로 바꾸는데 필요한 최소 비용을 구하고싶은데

그냥 bfs 돌리는게 최선인가요? 아니면 다른방법이 있나요?

[0xrgb(0xrgb)]

비용 정의가?

[익명(219.255)]

스왑 횟수만을 비용으로 해서요

[하루룽(ailedear)]

큰수부터 그 수를 맨 오른쪽까지 옮기는 데 비용이 몇 드는지 계산하고 제거하는거 반복

[하루룽(ailedear)]

맞나

[익명(219.255)]

예를들어 4231 에서 1234 만드는건 스왑 1번만 하면 되서 비용이 1인 식으로

[하루룽(ailedear)]

빡대가리엿다

[시아닌(kimjg1119)]

큐브러버한테 물어봤는데 답이 안나온걸 PS갤에 올린다고?

[익명(223.38)]

소트 방식 안 정해주고 찾으라는건 좀 어려운데.

[익명(223.38)]

NP 아니야?

[익명(223.62)]

전 이게 첫글이라 잘 모르는데 결국 탐색돌리는게 최선일까요

[치카냥￰(mlku124)]

나도 풀었는데 ㅇㅅㅇ;;;

[치카냥￰(mlku124)]

O(n) ㅇㅅㅇ;;