삽입정렬 횟수 세기 > 문제은행

본문 바로가기


실력키우기 자료처리

1814 : 삽입정렬 횟수 세기

제한시간: 1000 ms    메모리제한: 32 MB
해결횟수: 748 회    시도횟수: 1061 회   



임의의 서로 같지 않은 수로 이루어진 수열 A를 삽입정렬을 하고자 한다.

만약 배열 A에 20, 40, 30, 10 이 들어갈 경우 다음과 같이 삽입정렬이 이루어진다.

i = 1 일 때 20, 40, 30, 10 이동수 : 0
i = 2 일 때 20, 40, 30, 10 이동수 : 0
i = 3 일 때 20, 30, 40, 10 이동수 : 1 (40이 움직이고 30이 들어감)
i = 4 일 때 10, 20, 30, 40 이동수 : 3 (20, 30, 40 이 움직이고 10이 들어감)

총 4번의 밀어내기를 통하여 삽입정렬이 완료된다.

임의의 수열 A가 주어질 경우, 수열의 숫자가 얼마나 이동하는지 출력하는 프로그램을 작성하시오.


처음 줄에는 수열의 개수 N(1≤N≤50)이 입력된다. 다음 줄에는 N개의 -1000 이상 1000 이하의 정수가 입력된다. 이 수들은 서로 다르다고 가정한다.



입력된 수열에 대한 전체 이동 횟수를 출력하시오.


[Copy]
4
20 40 30 10
[Copy]
4


[Copy]
3
-1 1 0
[Copy]
1



HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.