(Baekjoon) GreedyAlgorithm - (14) 반도체 설계

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

2352번: 반도체 설계

 

이 문제를 풀기위해서

dp ->  2xn 타일링 -> 2xn 타일링2 -> 외판원순회 -> 타일채우기 -> bruteforce -> 부분수열의합 -> dp ->

-> lis O(n^2) -> list O(nlogn)

문제를 풀고 왔다. 너무나 오래걸렸다.

 

최장길이를 구하는 lis와 동일한 문제이다.

다만 n의 범위가 1<= n <= 40000 이라서 lowerbound를 사용하는 lis문제를 풀수 있어야 한다.

 

 

반도체 설계시에 최대로 설계가능한 값은 최장증가수열과 동일하다.

예를들어서 4 2 6 3 1 5 이 있을경우에

2 3 5 -> 가 최대로 설계가능한 방법이다.

그러므로 최장증가수열을 구한다면 바로 답이나온다.

package GreedyAlgorithm;

import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class _2352{

    static int n[] = new int[40001]; // 값 받는것
    static List<Integer> list;

    static int lowerbound(int n){
        int s = 0;
        int e = list.size();
        int m;
        while(s<e){
            m = (s+e)/2;
            if(list.get(m) < n) s = m + 1;
            else e = m;
        }
        return e;
    }
    public static void main(String args[]) throws IOException, NumberFormatException {


        list = new ArrayList<Integer>();
        list.add(0);

        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        for (int i = 1; i <= num; i++) {
            n[i] = sc.nextInt();
        }
        int lb;
        for (int i = 1; i < n.length; i++) {
            lb = lowerbound(n[i]);
            if(list.size() == lb)
                list.add(n[i]);
            else{
                if(list.get(lb) > n[i])
                    list.set(lb,n[i]);
            }    

        }

        System.out.println(list.size() - 1);

        sc.close();
    }
}

 

 

 

 

 

 

 

 

백준문제풀이Github : 

https://github.com/sdk0213/baekjoon-study

sdk0213/baekjoon-study