[C++] 소프티어 [인증평가 4차 기출] 통근버스 출발 순서 검증하기

https://softeer.ai/practice/info.do?idx=1&eid=654 

Softeer

풀이

정렬 불가능한 조합이 몇 개나 있는지 세는 문제이다.

Brute-Force로 모든 조합에 대해 검사할 경우 O(N^3)이기 때문에 5000^3 = 125,000,000,000 (1250초?) 이므로 다른 알고리즘이 필요하다.

Prefix Sum, 구간 합 개념을 사용한다면 O(N^2) 25,000,000 으로 1초 안에 계산을 마칠 수 있다.

1. 문제 조건에 의해 i < j < k 에 대해 a_k < a_i < a_j 의 조합을 찾아야 한다.

2. 이 때, 주어진 배열에서 a_i 와 a_j 를 결정했을 때 이미 정답(가능한 a_k의 수)을 알고 있으면 된다.

3. 이를 위해 a_i를 가능한 모든 수(1~N) 에 대해 돌려보면서 j 보다 오른쪽에 있는 수(a_k 후보)에 대해 a_k < a_i를 만족할 경우 카운트 해주면 된다.

4.  if ( arr[j] < num ) 은 a_k < a_i 를 확인한 것이고, 참일 경우 arr_1[i][j-1] 에 업데이트 한다. ( j는 j-1 보다 오른쪽에 있는 숫자다) 

5. 마지막으로 이중 for loop 로 가능한 모든 a_i < a_j 에 대해 arr_1[ arr[ i ] ][ j ] 를 통해 답을 업데이트 하면 된다. 

#include<iostream>
#include<vector>

using namespace std;

long long int answer = 0;

int main(int argc, char** argv)
{
	int n;
	int val;
	vector<int> arr;
	
	cin >> n;

	vector<vector<unsigned int>> arr_1(n+1, vector<unsigned int>(n,0));
	
	for (int i = 0; i < n; i++) {
		cin >> val;
		arr.push_back(val);
	}

	// j보다 오른쪽에 있는 수 중에, a_k < a_i(임의의 자연수) 만족하는 개수 찾기
	for (int num=1; num<=n; num++) {
		for (int j = n-1; j>=1; j--) {
			if (arr[j] < num) {
				arr_1[num][j-1] = arr_1[num][j] + 1;
			}
			else {
				arr_1[num][j-1] = arr_1[num][j];
			}
		}
	}

	for (int i=0; i<n-2; i++) {
		for (int j=i+1; j<n-1; j++) {
			if (arr[i] < arr[j]) {
				answer += arr_1[arr[i]][j];
			}
		}
	}
	cout << answer << endl;
	return 0;
}