2020.06.05 백준2352 반도체 설계, ssafy 준비...

1 2 3 4 5 6 7 8 9 10 11

public static int lower_bound(int []arr,int left,int right,int obj) {         int front=left;         int rear=right;         int mid;         while(rear>front) {             mid=(front+rear)/2;             if(arr[mid]<obj) front=mid+1;             else rear=mid;         }         return rear;     }

cs

일반적인 이분탐색과는 다르게 찾으려는 obj 값이 mid 위치의 값보다 작으면 rear=mid 위치 시키면서 좁혀 나간다.

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46

import java.util.ArrayList; import java.util.Scanner;   //반도체 설계 public class boj2352 {     static int n;     static int line[];     public static void main(String[] args) {         Scanner sc=new Scanner(System.in);         ArrayList<Integer> list=new ArrayList<>();         n=sc.nextInt();         line=new int[n];         for(int i=0;i<n;i++) {             line[i]=sc.nextInt();         }                  System.out.println(solve(list));         sc.close();     }          public static int solve(ArrayList<Integer> list) {         list.add(line[0]);         for(int i=1;i<n;i++) {             int idx=lower_bound(list, 0, list.size(), line[i]);             if(idx==list.size()) list.add(line[i]);             else {                 list.remove(idx);                 list.add(idx,line[i]);             }         }         return list.size();     }          public static int lower_bound(ArrayList<Integer> list,int left,int right,int obj) {         int front=left;         int rear=right;         int mid;         while(rear>front) {             mid=(front+rear)/2;             if(list.get(mid)<obj) front=mid+1;             else rear=mid;         }         return rear;     } }

cs

lis 이긴하지만,n^2로 풀면안되고 이분탐색을 사용한 nlogn 방식으로 풀어야 한다.

정렬이 안되어있는데 어떻게 이분탐색을 쓰는거지 싶었다.

4 2 6 3 1 5  라고 되어있을 때,

4 > 2 > 2 6 > 2 3 > 1 3 > 1 3 5  식으로 변형해 나간다. 1 3 5 로 이렇게 끝나는게 제대로 된 설명을 찾으려해도 없고 이해가 좀 안가긴 한다...중요한 것은 lis 문제는 lowerbound를 이용하자! 를 숙지할 것!

 

하 안떨렸었는데 하루 전이니깐 떨린다... ct부분이 걱정이다...