[Algorithm] 99클럽 코테 스터디 4일차 TIL | 백준_기타 레슨(2343번)

2025. 1. 16. 12:30·Algorithm

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


오늘도 이분탐색..^^

문제의 접근 방법에 대해서만 살짝 gpt한테 엿듣고

 

low를 가장 긴 녹화 길이로,

high를  모든 녹화 길이의 합으로 설정한 후

 

블루레이 크기를 mid로 잡는 것을 시작으로 차근차근 풀어나간 문제다.

(답을 보지않고 맞혔다는 것에 큰 희열 🥲 나..이제 이분탐색 마스터?)

 

이 문제의 핵심은 mid 값으로 잘랐을 때 M개로 나눌 수 있는가? 이다.

 

만약 나눈 값이 M보다 크면

mid 값을 더 크게 잡아야 하므로 low = mid + 1을 해주고

 

나눈 값이 M보다 작거나 같다면 

mid값을 더 작게 잡아야 하므로 high = mid - 1을 해준다.

이때 정답이 나올 수 있으므로 result값에 mid를 넣어주었다. (최솟값을 찾아야하므로,,)

if(cnt <=  M){
    high = mid - 1;
    result = mid;
}else{
    low = mid + 1;
}

 

전체 풀이

import java.util.*;
import java.io.*;
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 N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[] arr = new int[N];

        int max = 0;
        int sum = 0;

        st = new StringTokenizer(br.readLine(), " ");

        for(int i = 0; i < N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
            max = Math.max(max, arr[i]);
            sum += arr[i];
        }

        int low = max;
        int high = sum;
        int result = 0;

        while(low <= high){
            int mid = (low + high) / 2;

            int key = 0;
            int cnt = 1;

            for(int i = 0; i < N - 1; i++){
                key += arr[i];
                if(mid < key + arr[i+1]){
                    cnt++;
                    key = 0;
                }
            }
            if(cnt <=  M){
                high = mid - 1;
                result = mid;
            }else{
                low = mid + 1;
            }
        }
        System.out.println(result);
    }
}

 

오늘은 공책에 필기해가면서 풀었더니 더 정리가 잘 되는 느낌이다.

역시 암산은 나랑 안 맞아(?)

 

 

'Algorithm' 카테고리의 다른 글

[Algorithm] 99클럽 코테 스터디 6일차 TIL | 백준_DFS와 BFS(1260번)  (4) 2025.01.20
[Algorithm] 99클럽 코테 스터디 5일차 TIL | 백준_두 용액(2470번)  (0) 2025.01.17
[Algorithm] 99클럽 코테 스터디 3일차 TIL | 백준_선분 위의 점(11663번)  (1) 2025.01.15
[Algorithm] 99클럽 코테 스터디 2일차 TIL | 백준_랜선 자르기(1654번)  (0) 2025.01.14
[Algorithm] 99클럽 코테 스터디 1일차 TIL | 백준_암기왕(2776번)  (0) 2025.01.13
'Algorithm' 카테고리의 다른 글
  • [Algorithm] 99클럽 코테 스터디 6일차 TIL | 백준_DFS와 BFS(1260번)
  • [Algorithm] 99클럽 코테 스터디 5일차 TIL | 백준_두 용액(2470번)
  • [Algorithm] 99클럽 코테 스터디 3일차 TIL | 백준_선분 위의 점(11663번)
  • [Algorithm] 99클럽 코테 스터디 2일차 TIL | 백준_랜선 자르기(1654번)
dev_ajrqkq
dev_ajrqkq
알고리즘 천재가 될 거야
  • dev_ajrqkq
    기록이 자산이다
    dev_ajrqkq
  • 전체
    오늘
    어제
    • 분류 전체보기 (147)
      • Front-end (0)
      • Back-end (11)
        • Spring (1)
        • Java (8)
      • CS (9)
        • 데이터베이스 (5)
        • 네트워크 (4)
      • Algorithm (80)
      • 이것저것 (0)
      • 버그잡기 (1)
      • TIL (37)
      • 후기 (1)
      • 취준 (0)
  • 블로그 메뉴

    • 링크

    • 공지사항

    • 인기 글

    • 태그

      티스토리챌린지
      Til
      TypeScript
      99클럽
      개발자취업
      코딩테스트준비
      항해99
      오블완
    • 최근 댓글

    • 최근 글

    • hELLO· Designed By정상우.v4.10.2
    dev_ajrqkq
    [Algorithm] 99클럽 코테 스터디 4일차 TIL | 백준_기타 레슨(2343번)
    상단으로

    티스토리툴바