[소프티어] 통근버스 출발 순서 검증하기 / C++ 해설

더 많은 문제풀이는 아래 Github 주소에서 확인하실 수 있습니다.

https://github.com/Dongha-k/softeer-code

GitHub - Dongha-k/softeer-code: softeer 문제 풀이입니다.

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

Softeer

소프티어 공식해설: https://softeer.ai/community/view.do?idx=731&cd=edu&pageNo=1

Softeer

 

알고리즘 분류: DP

주의할 것: 시간복잡도

 

#include <iostream>

using namespace std;

int main(int argc, char** argv)
{
	int n;
	int arr[5000];
	int d[5001];
	unsigned long long res = 0;
	cin >> n;
	for(int i = 0 ; i < n ; i ++) cin >> arr[i];
	for(int i = 0 ; i < n ; i ++){
		for(int j = 0 ; j <= n ; j ++) d[j] = 0;
		for(int j = 0 ; j < i ; j ++) if(arr[i] > arr[j]) d[arr[j]] = 1;
		for(int j = n - 1; j > 0 ; j --) d[j] += d[j + 1];
		for(int j = i + 1 ; j < n ; j ++) res += d[arr[j]];
	}
	cout << res;
	return 0;
}

 

설명:

 

문제가 길었다. 스택수열과 관련있는 문제일줄알고 문제를 읽으면서 스택을 사용해야하나라고 생각하였지만 결국 i < j < k 이면서 a_i < a_j 이고 a_i > a_k를 만족하는 순서쌍 (i, j, k)의 모든 갯수를 찾는 문제였다.

 

Trial 1: N개 중 만들 수 있는 3개의 가능한 모든 순서쌍을 추출한 뒤 위의 조건을 만족하면 정답에 1을 더한다.

Result: 시간초과가 발생하였다. n이 5000까지 올 수 있으므로 최대로 걸리는 시간은 n = 5000일 때 5000C3으로 거의 5000 ^3 의 연산이 수행되어야 한다. 이는 약 125000000000의 값이다.. 당연히 시간초과난다. 그만알아보자...

 

Trial 2: DP와 관련된 누적합을 응용한 풀이를 하였다. i < j < k이면 j 기준에서 왼쪽에 있는 a_i는 a_j보다 작아야한다. 또한 a_k < a_i 이어야하므로 a_k < a_i < a_j를 만족해야한다.

for(int i = 0 ; i < n ; i ++){ // 1
	for(int j = 0 ; j <= n ; j ++) d[j] = 0; // 2
	for(int j = 0 ; j < i ; j ++) if(arr[i] > arr[j]) d[arr[j]] = 1; // 3
	for(int j = n - 1; j > 0 ; j --) d[j] += d[j + 1]; // 4
	for(int j = i + 1 ; j < n ; j ++) res += d[arr[j]]; // 5
}

 

1. i < j < k 기준으로 j를 중심으로 a_k < a_i < a_j을 만족하는 순서쌍을 찾으려고 하였기에 j를 0부터 n - 1까지 돌렸다.

2. 배열 d는 a_i < a_j를 만족하면서 d[v]의 경우 v값보다 크거나 같은 a_i의 갯수를 나타낸다.

3. i < j이면서 a_i < a_j일 경우 d[a_i] = 1로 만들어준다.

4. 배열 d[k]를 a_i < a_j를 만족하는 k보다 같거나 큰 수의 갯수를 나타내기 위해서 누적합을 이용하였다. 즉, d[3]이라는 값은 3보다 같거나 크면서 a_i < a_j를 만족하는 수의 갯수를 나타낸다. 만약 d[3]이 0이라면 이를 만족하는 순서쌍이 없다는 뜻과 같다.

5. 인덱스 k를 순회하면서 d[a_k]는 a_i < a_j를 만족하는 a_k보다 같거나 큰 a_i의 갯수이므로 이 값이 3이면 a_k < a_ i < a_j를 만족하는 순서쌍 수가 3개라는 뜻이므로 정답에 +3을 해준다.

 

Result: 성공

 

주의할 점: 시간복잡도

 

위 코드는 시간복잡도 O(N^2)을 가진다. Trial 1의 경우 for문을 세번 반복하는 경우와 같고 Trial 2의 경우 for문을 두번만 반복하는 경우이므로 5000 * 5000 = 25000000으로 시간안에 들어오게 되었다.