2352번 문제

문제

풀이

구상

전형적인 LIS 문제.
어떤 포트 i를 선택한다고 가정했을 때, 연결선이 서로 꼬이지 않기 위해서는
- i보다 작은 인덱스 j에 대해 선택포트[j] < 선택포트[i] 여야 함
- i보다 큰 인덱스 j에 대해 선택포트[j] > 선택포트[i] 여야 함.

즉, 그냥 인덱스가 증가하는 방향으로, 연결되어야 하는 포트가 계속해서 증가되는 부분 순열을 찾으면 된다.

LIS 풀이의 정석으로 이분탐색을 통해 풀었다.

최종 제출 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static int[] memo;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int len = 0;
        int idx = 0;
        memo = new int[n+1];
        for(int i=0; i<n; i++) {
            if(arr[i] > memo[len]) {
                len++;
                memo[len] = arr[i];
            } else {
                idx = binarySearch(0, len, arr[i]);
                memo[idx] = arr[i];
            }
        }
        System.out.println(len);
    }

    static int binarySearch(int left, int right, int key){
        int mid = 0;
        while(left < right) {
            mid = (left+right)/2;
            if(memo[mid] < key) {
                left = mid+1;
            } else {
                right = mid;
            }
        }
        return right;
    }
}

LIS는 잊지 않도록 가끔씩 풀어주면 좋을 것 같다.