취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 3061번 문제인 사다리이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/3061 

사다리 선을 하나 긋는 것은 인접한 두 원소의 차례를 서로 바꾸는 것과 같음을 알 수 있다.

위의 관찰과 함께 사다리의 위아래를 뒤집어 문제를 재해석하면, 주어진 배열을 버블정렬(bubble sort)할 때 필요한 최소 swap 횟수를 구하는 문제로 생각할 수 있다. 이 값을 계산해 문제를 해결하자.

아래는 제출한 소스코드이다.

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

int T, N;
int arr[1001];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> T;
	while (T--) {
		memset(arr, 0, sizeof(arr));
		int ans = 0;
		cin >> N;
		for (int i = 0; i < N; i++) {
			int x; cin >> x;
			for (int j = x + 1; j <= N; j++) ans += arr[j];
			arr[x] = 1;
		}

		cout << ans << '\n';
	}
}