[백준] 2352번 반도체 설계

문제 설명

• https://www.acmicpc.net/problem/2352
• Gold 2
• 소요 시간 : 12분

문제 풀이

• LIS 문제이다. DP로 풀이하였다.
• 문제에서 N의 범위가 40000이므로 O(NlogN)알고리즘을 이용해야 한다.
• 이전 포스팅 설명 참조

소스 코드 (JAVA)

import java.io.*;
import java.util.*;
class Main {

    static BufferedWriter bw;
    static BufferedReader br;

    static int N;
    static int[] arr;

    static int[] dp;  // dp[i] : 길이가 i+1인 LIS의 가장 작은 번호

    // value 이상인 수가 처음 나오는 인덱스 반환
    static int lowerBound(int lo, int hi, int value) {
        while(lo + 1 < hi) {
            int mid = (lo + hi) / 2;
            if (dp[mid] < value) lo = mid;
            else if (dp[mid] > value) hi = mid;
            else hi = mid;
        }
        return hi;
    }

    static void solve() throws IOException {
        int len = 1;
        dp[0] = arr[0];
        for (int i = 1; i < N; i++) {
           int index = lowerBound(-1, len, arr[i]);
           dp[index] = arr[i];
           if (index == len) len++;
        }
        bw.write(len + "\n");
        bw.flush();
    }


    static void input() throws IOException {
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        dp = new int[N];
        arr = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++)
            arr[i] = Integer.parseInt(st.nextToken());
    }

    public static void main(String[] args) throws IOException {
        input();
        solve();
    }
}

/**
 * 반도체 설계 (18:49)
 *
 * - N개 - N개 연결 중 연결선이 꼬이지 않으면서 최대 몇개까지 연결할 수 있는가
 * - LIS(최대 증가 수열)
 *
 * - N (<=40000)
 * - O(NlogN) 풀이로 풀어야함
 *
 * N
 * a1 a2 ... an
 */