[C++] 소프티어 [인증평가 4차 기출] 통근버스 출발 순서 검증하기
https://softeer.ai/practice/info.do?idx=1&eid=654 Softeer 문제에서 주어진 조건을 만족하는 서로 다른 (i, j, k) 순서쌍의 개수를 출력한다. 첫 번째 위치에는 2번 버스, 두 번째 위치에는 3번 버스, 그리고 세 번째 위치에는 1번 버스가 기다 softeer.ai 풀이 정렬 불가능한 조합이 몇 개나 있는지 세는 문제이다. 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 에 대..
2023. 1. 18.