초인 샘은 초등학교 3학년 선생님이다. 학기 초에 새로운 학생들을 만나면 학생들의 키를 기준으로 오름차순으로 정렬하여 번호를 매겨준다. 그런데 학생들에게 오름차순(키 작은 학생부터 큰 학생 순)으로 줄을 서라고 하면 모두가 움직이므로 대 혼란이 발생한다. 그래서 생각한 것이 아래와 같은 방법으로 줄을 세우기로 했다.

[초인 샘의 줄 세우기] 1. 첫 번째 학생을 1번 자리에 세운다. 2. 두 번째 학생을 2번 자리에 세운다. 2번 자리 학생이 1번 자리 학생보다 크면 그대로 둔다.그렇지 않으면 1번 자리 학생과 2번 자리 학생의 위치를 바꾼다. 3. 현재 N명이 줄 서 있다고 할 때 N+1번 자리에 N+1번째 학생을 세운다. N+1번째 학생은 N번부터 1번 학생까지 차례로 비교하면서 자신보다 큰 학생이면 자리를 바꾼다. 그렇지 않은 경우 자리바꿈을 종료한다.

이렇게 자리바꿈할 경우 자리바꿈 횟수는 얼마나 될까?

#2853 upload 115 done 65 how_to_reg 61

초인 샘의 줄 세우기 timer 1s memory 16MB

#2853

초인 샘의 줄 세우기 1s 16MB