[기출 상] 집으로 가는 길(사다리 타기 문제) - 정렬

[문제]

초기의 사람 배치 순서를 입력받아 각 사람이 자신의 집으로 돌아갈 수 있게 하는 최소 개의 다리의 수를 return 하도록 해라. 예를 들어 [3, 2, 1, 4] 의 순서대로 있는 사람이 [1, 2, 3, 4]의 자신의 집으로 돌아가기 위해 놓아야 하는 최소한의 사다리 개수는 3개이다.

 

[풀이]

사다리 문제의 규칙을 알아내는 것이 중요하다. 사람이 3, 2, 1, 4의 순서로 배치되어있다고 하자. 3과 2 사이에 사다리를 하나 놓으면 [2, 3, 1, 4]로 사다리 왼쪽, 오른쪽 순서가 바뀌는 것을 알 수 있다. 3과 1 사이에 하나 더 놓으면 [2, 1, 3, 4]로, 2와 1 사이에 하나 더 놓으면 [1, 2, 3, 4]로 순서가 바뀌므로 최소 3개의 사다리를 놓아야 한다. 따라서 이는 정렬을 이용하여, 정렬(swap)이 일어날 때마다 answer을 증가시켜주면 된다. 이때, 사람 수(100,000)에 비해 사다리는 훨씬 많이 놓아야 할 수 있으므로 long long으로 선언한다.

 

[코드]

#include<iostream>
#include<string>
using namespace std;


long long solution(int n, int* list) {
	long long answer = 0;
	int i, j;
	//사다리를 하나 놓으면 사다리 왼, 오 두 자리가 swap 됨.
	for (i = 1; i < n; i++) {
		for (j = i-1; j >= 0; j--) {
			if (list[j] > list[i])
				answer++;
				//list[j + 1] = list[j];
		}
		//list[j + 1] = list[i];
	}

	return answer;
}

int main()
{
	//각 사람이 자신의 집으로 돌아갈 수 있는 최소 다리의 개수 return
	int n;
	int list[100000];
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> list[i];
	}

	cout << solution(n, list);
}