playsworld16   3년 전

*이 글에는 제 논리가 설명되어 있습니다. 만약 이 문제를 스스로 풀 생각이시고, 이 글이 그걸 방해할 것 같다면 뒤로가기를 누르는 걸 추천드립니다. 

전 다음과 같은 논리로 해결하려고 했습니다.

1. 탐색하지 않은 추 중 가장 무게가 낮은 것(A)을 찾는다. 

2.1 만약 A의 현재 위치가 정렬했을 때의 위치와 같다면 1로 돌아간다.

2.2 A의 위치를 "정렬했을 때 자신의 현재 위치로 오는 추"와 바꾼다. 이 과정에서 두 추의 무게의 합을 ans에 더한다.

3. 2를 반복한다.

여기서 2를 무조건 반복하다 보면 언젠가 정렬된 위치로 간다고 생각했습니다. 증명은 없고 단순한 감입니다...

(맞다면 왜 맞은지, 틀리면 왜 틀린지 설명해주시면 감사합니다)

논리에 문제가 있는 것인지, 코딩하는 과정에서 문제가 생긴 것인지조차 모르겠습니다.

도와주시면 감사하겠습니다.

-- 코드 내림 --

dhkang01   3년 전

알고리즘이 잘못 되었습니다. 반례가 있습니다. 아래 반례의 정답은 5016입니다.

playsworld16   3년 전

답변 감사합니다! 덕분에 맞췄습니다.

댓글을 작성하려면 로그인해야 합니다.