[BOJ/백준] 2352. 반도체 설계 (Java)

🔎문제

https://www.acmicpc.net/problem/2352

2352번: 반도체 설계

 

💡풀이

LIS(가장 긴 증가하는 부분 수열) 문제이다. (백준에 시리즈로 있는 LIS 문제들은 따로 정리해놓은것이 있으니 참고하세요😊)

 

지정된 포트들을 연결하면서, 가장 많이 연결하면 된다.

뒷쪽 포트가 앞보다 더 앞 포트를 연결하면 안되므로, 뒤로 갈수록 큰 숫자의 포트를 연결해야한다.

따라서 증가하는 수열을 구하면 되는 것이고, 가장 긴 것을 구하는것이므로 LIS문제와 똑같다.

 

📃소스코드

  

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


public class Main {

    public static int n;

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

        int[] memo = new int[n];
        int size = 0;
        for (int i = 0; i < n; i++) {
            int idx = Arrays.binarySearch(memo, 0, size, nums[i]);
            if (idx < 0) idx = idx * (-1) -1;
            memo[idx] = nums[i];
            if (idx == size) size++;
        }

        System.out.println(size);
    }
}