[백준/BOJ]3061. 사다리 [Silver 3]

3061. 사다리

문제출처 : https://www.acmicpc.net/problem/3061

아직 시험기간이긴 하지만, 주말이 남아있어서 정말 오랜만에 블로그 포스팅도 할겸 감도 찾을겸 백준을 풀었다. 알고리즘 시험공부는 하기싫은데 이런 알고리즘은 왜 나를 두근거리게 하는지...

와.... 이건진짜 생각도 못한문제였다.
사다리줄긋는 알고리즘을 한번도생각안해봐서, 왼쪽으로가면 음수, 오른쪽으로가면 양수로 나눠서 생각해야하나? 하면서 계속고민하다가, 백준 질문코너를 갔더니 한분이 정렬을 하고 있더라.
아니, 정렬해야할게 없는데? 왜 정렬을 하지? 그러다가
아! 1번과 2번사이 사다리 한줄을 긋는다는것은 1번과 2번의 자리를 바꾸는것과 같다는 것을 깨달았다.

code

#include <stdio.h>
int main()
{
	int T, N, RP[1001] = { 0 }, i, j, temp;
	scanf("%d", &T);
	while (T)
	{
		int count = 0, index = 1;
		scanf("%d", &N);
		for (i = 1; i <= N; i++)
			scanf("%d", &RP[i]);
		for (i = 1; i <= N; i++)
		{
			for (j = i; j <= N; j++)
				if (i == RP[j])
					index = j;
			while (RP[i] != i)
			{
				temp = RP[index - 1];
				RP[index - 1] = RP[index];
				RP[index] = temp;
				index--;
				count++;
			}
		}
		printf("%d\n", count);
		T--;
	}
	return 0;
}

사다리 줄을 긋는다고 생각하니까 엄청 복잡했는데, 자리를 바꾼다고 생각하니까 엄청 쉽게 풀렸다. 단지 반복문이 조금많을뿐...