[JAVA] 백준 이진탐색 뿌수기1

 

이진탐색이 너무 약해서 뿌수기 시리즈를 해보려고한다

 

 

 

 

10815 숫자 카드 - 실버5

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

10815번: 숫자 카드

• 정말 이진탐색만 하면 되는 문제다

 

class Main {
    public static void main(String[] args) throws IOException {
        StringBuilder sb = new StringBuilder();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int cnt = Integer.parseInt(br.readLine());
        int[] arr = new int[cnt];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i =0; i<arr.length; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(arr);

        int cnt2=  Integer.parseInt(br.readLine());

        st = new StringTokenizer(br.readLine());
        for (int i =0; i<cnt2; i++) {
            int number=  Integer.parseInt(st.nextToken());

            int start = 0;
            int end=  arr.length;

            boolean isEnd = false;
            while (start < end) {
                int mid = (start + end)/2;
                if (arr[mid] == number) {
                    sb.append(1 + " ");
                    isEnd = true;
                    break;
                }

                if (arr[mid] < number)
                    start = mid+1;
                else
                    end = mid;
            }

            if (!isEnd)
                sb.append(0 + " ");
        }

        System.out.println(sb);
    }
}

 

 

 

 

1920 수 찾기 - 실버4

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

1920번: 수 찾기

• 위 문제와 너무 동일해서 코드를 올리기도 민망하다
• 위 문제의 코드에서 줄바꿈만 해주면 됨

 

 

 

 

1072 게임 - 실버3

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

1072번: 게임

• 이전에는 수학적인 방식으로 계산했는데, 이번에는 이진탐색을 써보기로 했다.
• 시간복잡도가 그냥 계산하는 것보다 훨씬 줄어들어서 신기하다

 

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        long x = Long.parseLong(st.nextToken());
        long y = Long.parseLong(st.nextToken());

        long prev = y*100/x;
        if (prev == 100 || prev == 99) {
            System.out.println(-1);
            return;
        }

        long start = 1;
        long end = 1000000001;

        //lower bound
        while (start < end) {
            long mid = (start + end)/2;

            long value = (mid + y) * 100 / (mid + x);

            if (value >= prev+1)
                end = mid;
            else
                start = mid+1;
        }

        System.out.print(start);
    }
}

• 최댓값인 10억으로 end를 지정하고 이진탐색으로 원하는 값을 찾았다
• 소수점 버림하여 원하는 값이 여러 개 나올 수 있기 때문에 그 중 가장 작은 값을 고르기위해 lower bound를 썼다

 

 

 

7795 먹을 것인가 먹힐 것인가 - 실버3

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

7795번: 먹을 것인가 먹힐 것인가

• 둘 다 정렬하기에는 시간이 많이 걸릴 것 같아 탐색대상만 정렬해줬다
• (m+n)logm 시간이 걸린다

 

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tcCnt = Integer.parseInt(br.readLine());
        StringBuilder sb =new StringBuilder();

        for (int t=0; t<tcCnt; t++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int aCnt = Integer.parseInt(st.nextToken());
            int bCnt = Integer.parseInt(st.nextToken());

            int[] arr1 = new int[aCnt];
            st = new StringTokenizer(br.readLine());
            for (int i =0; i<aCnt; i++) {
                arr1[i] = Integer.parseInt(st.nextToken());
            }

            int[] arr2 = new int[bCnt];
            st = new StringTokenizer(br.readLine());
            for (int i =0; i<bCnt; i++) {
                arr2[i] = Integer.parseInt(st.nextToken());
            }

            Arrays.sort(arr2);

            int cnt = 0;

            for (int i =0; i<aCnt; i++) {
                int canEat = arr1[i]-1;

                int start = 0;
                int end = arr2.length;

                while (start < end) {
                    int mid = (start + end)/2;

                    if (arr2[mid] <= canEat) {
                        start = mid + 1;
                    } else {
                        end = mid;
                    }
                }

                cnt += start;
            }

            sb.append(cnt + "\n");
        }

        System.out.print(sb);
    }
}

 

 

 

1654 랜선 자르기  - 실버2

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

1654번: 랜선 자르기

• 무조건 N개의 랜선을 만들 수 있기 때문에 조건을 만족하는 랜선의 최대 길이를 찾으면 된다
• 만족하는 길이를 찾아내기위해 길이 1부터 적당한 길이까지 이진탐색을 통해 찾으면 되겠다
  • 만족하는 게 무조건 존재하고, 만족하는 게 여러 개 존재할 수 있으며, 그 중 가장 큰 애를 찾는 것이기 때문에 upperbound 를 쓰면 되겠다

 

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int k = Integer.parseInt(st.nextToken());
        int required = Integer.parseInt(st.nextToken());
        int[] arr = new int[k];

        int maxLen = -1;
        for (int i =0; i<k; i++) {
            arr[i] = Integer.parseInt(br.readLine());
            
            if (maxLen < arr[i])
                maxLen= arr[i];
        }

        //랜선의 길이
        long start = 1;
        long end = (long)maxLen+1;

        while (start < end) {
            long mid = (start + end)/2;

            long cnt = 0;
            for (int a : arr) 
                cnt += a/mid;

            if (cnt >= required) 
                start = mid+1;
            else 
                end = mid;

        }

        System.out.println(start-1);
    }
}

• int 범위를 왔다갔다 하기 때문에 이 부분만 조심하면 되겠다

 

 

 

 

2805 나무 자르기 - 실버2

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

2805번: 나무 자르기

• 높이값을 기준으로 이진탐색을 사용해야겠다
• 항상 필요한 값을 가져갈 수 있기 때문에 upper bound를 사용하고 -1을 해줄 것이다
  • 해당 높이에서 필요한 나무는 직접 세야할듯
• 랜선 자르기와 다를 게 없다

 

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int treeCnt = Integer.parseInt(st.nextToken());
        int requiredSum = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        int[] height = new int[treeCnt];

        int maxHeight = -1;
        for (int i=0; i<height.length; i++) {
            height[i] = Integer.parseInt(st.nextToken());
            if (maxHeight < height[i])
                maxHeight = height[i];
        }

        int start = 0;
        int end = maxHeight;

        while (start < end) {
            int mid = (start + end)/2;

            long cnt = 0;
            for (int h: height) {
                cnt += Math.max(0, h - mid);
            }

            if (cnt >= requiredSum) {
                start = mid+1;
            } else {
                end = mid;
            }
        }

        System.out.println(start -1);
    }
}

 

 

 

 

2343 기타 레슨 - 실버1

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

2343번: 기타 레슨

• 블루레이의 크기를 이진탐색으로 찾아주면 될 것 같다
• 최솟값을 구하는 거라서 lower bound를 사용해 줄 것이다
• start는 강의의 최대 길이로 설정해주고, end는 강의들의 길이 합으로 설정하면 가능한 블루레이 크기가 정해진다

 

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int courseCnt = Integer.parseInt(st.nextToken());
        int blurayCnt = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        int[] course = new int[courseCnt];
        int sum = 0;
        int max = 0;
        for (int i=0; i<courseCnt; i++) {
            course[i] = Integer.parseInt(st.nextToken());
            sum += course[i];
            if (max < course[i])
                max = course[i];
        }

        int start = max; //강의 최대 길이
        int end = sum+1; //강의들 합 = 블루레이가 하나일 때

        while (start < end) {
            int mid = (start + end)/2;

            int prev = 0;
            int tmpCnt = 0;
            for (int len: course) {
                if (prev + len > mid) {
                    tmpCnt ++;
                    prev = len;
                } else {
                    prev += len;
                }
            }

            tmpCnt++;
            if (tmpCnt > blurayCnt)
                start = mid+1;
            else
                end = mid;
        }

        System.out.println(start);
    }
}