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

 

https://softeer.ai/practice/6257

 조건을 만족하는 (i, j, k)를 찾기 위해 3중 loop를 돌린다면 O(n³)의 시간복잡도를 가지므로 시간 제한을 초과할 것이다. 따라서 DP를 이용해 (i < j, a_i < a_j)를 만족하는 i, j와 (i < k, a_i < a_k)를 만족하는 i, k를 따로 구하여 O(n²) 시간복잡도로 문제를 해결할 수 있다.

 

[ 풀이 방법 ]

1. i를 선택하고, i < j와 a_i < a_j를 모두 만족하는 j의 개수를 구하는 기능

  - loop를 돌며 dp[i][j]에 a_i보다 큰 a_j의 개수 저장

 

2. i를 선택하고 i < k와 a_i < a_k를 모두 만족하는 k를 구하여 결과를 구하는 기능

  - loop를 돌며 a_i와 a_k를 비교하고 a_k가 더 작다면 res에 dp[i][k-1](i와 k사이의 모든 조건을 만족하는 수의 개수)을 더해준다. 

 

[ 회고 ]

 완전탐색을 사용하기에 시간복잡도가 문제가 되는 문제였기 때문에 DP를 떠올렸어야 했으나 풀이 방법을 생각하지 못했다. 따라서 다른 사람의 풀이 방법을 보고나서야 풀이 방법을 생각할 수 있었다.

 

 앞으로 비슷한 문제가 나오면 DP를 떠올릴 수 있도록 해야 할 것이며, DP에 대한 학습이 더 필요하다고 느꼈다.

 

[ 정답 코드 ]

#include<iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main(int argc, char** argv)
{
    iostream::sync_with_stdio(0);
    cin.tie(0);

    unsigned long long res = 0;

    int N;
    cin >> N;
    vector<int> v(N);
    vector<vector<int>> dp(N, vector<int>(N));

    for(int i = 0; i < N; i++) {
        cin >> v[i];
    }
    
    for(int i = 0; i < N-2; i++) {
        int cnt = 0;
        for(int j = i+1; j < N-1; j++) {
            if(v[i] < v[j]) cnt++;
            dp[i][j] = cnt;
        }
    }

    for(int i = 0; i < N-2; i++) {
        for(int j = i+2; j < N; j++) {
            if(v[i] > v[j]) res += dp[i][j-1];
        }
    }
    
    cout << res;

   return 0;
}