[sof] 소프티어 <인증평가 4차 기출> 통근버스 출발 순서 검증하기 (Java) - 구간합

[문제]

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

Softeer

 

[풀이]

i, j, k 3중 for문을 돌리거나 dfs로 3가지 순열을 찾아서 ai<aj, ai>ak를 만족하는지 확인하면 풀 수 있다. 그러나 당연히 시간초과가 발생하기에...효율적으로 푸는 방법을 생각해내야 하는데 아아무 생각도 나지 않았고, 소프티어에서 제공해준 모범답안을 확인했다. 

 

1. 먼저 arr[x][j]는 j보다 오른쪽에 있는 배열 값들에 대해 x보다 작은 수들의 개수를 의미한다. 배열의 끝부분부터 탐색을 진행하면 bus[j+1] < x일 때, arr[x][j] = arr[x][j+1]+1 로 채워나갈 수 있다. 

j가 n-1일 때는 오른쪽에 값이 없으므로 x보다 작은 수들의 개수는 모두 0이다. 따라서 n-2부터 탐색을 진행하였다.

 

2. i, j 2중 for문을 돌려서 i<j 이고, ai<aj 일 때의 ai>ak를 만족하는 i,j,k의 개수를 구할 수 있다. arr[bus[i]][j]는 j<k에 대해서 ai>ak를 만족하는 수들의 개수이기 때문이다. 

 

따라서 O(n^2)만으로 답을 구할 수 있다!

 

그리고 N이 최대 5000이므로 answer의 자료형을 long으로 설정해야 함을 주의하도록!!!

 

 

[코드]

 

import java.util.*;
import java.io.*;


public class Main
{
    static int[] bus;
    static int[][] arr;
    static long answer;
    static int n;
    public static void main(String args[]) throws Exception
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        bus = new int[n+1];
        arr = new int[n+1][n+1]; //arr[x][j] -> j보다 오른쪽에 있는 수들에 대해서 x보다 작은 수들의 개수
        for(int i=0; i<n; i++){
            bus[i] = Integer.parseInt(st.nextToken());
        }

        //arr[x][j] 채우기
        for(int j=n-2; j>=0; j--){
            for(int x=1; x<=n; x++){
                if(bus[j+1] < x){
                    arr[x][j] = arr[x][j+1] + 1;
                }
                else{
                    arr[x][j] = arr[x][j+1];
                }
            }
        }

        //i<j<k에 대해서 ai<aj, ai>ak 인 경우의 수 구하기
        for(int i=0; i<n-2; i++){
            for(int j=i+1; j<n-1; j++){
                if(bus[i]<bus[j]){
                    answer += arr[bus[i]][j]; //j보다 오른쪽에 있는 수(ak)들 중 ai보다 작은 경우의 개수
                }
            }
        }

        System.out.println(answer);

    }

}