[백준] 2343. 기타 레슨 - C++

문제

---

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

 

• 소요 시간 : 40분
• 난이도 : 실버 1

접근 방법

---

 

블루레이의 최소 길이를 구하기 위해 이분탐색을 이용한다.

 

1. left, right 값 초기화

left 값 : 강의 길이 중 최댓값 ->  블루레이 개수 N개

right 값 : 모든 강의 길이의 합 -> 블루레이 개수 1개

 

2. 체크

강의를 돌면서 블루레이에 1개씩 강의 길이를 더해준다.

초과되면 블루레이 개수를 1개 더하고 새 블루레이에 더해준다.

블루레이 개수가 M보다 많아지면 중단한다.

 

3. 정답 갱신 및 이분탐색 범위 조정

블루레이 개수가 M보다 크면 더 길게 담아도 되므로 left를 늘린다. 

블루레이 개수가 M보다 작거나 같으면 더 작게 담아도 되므로 right를 줄인다. 

ex. N = 9, M = 3, 강의 = [1, 2, 3, 4, 5, 6, 7, 8, 9]

1. left = 9, right = 45, mid = (9+45)/2 = 27
블루레이 개수 : 1~6, 7~9 = 2개 
M보다 작으므로 right = mid-1 = 26

2. left = 9, right = 26, mid = (9+26)/2 = 17 
블루레이 개수 : 1~5, 6~7, 8~9 = 3개 
M과 같으므로 right = mid-1 = 16

3. left = 9, right = 16, mid = (9+16)/2 = 12
블루레이 개수 : 1~5, 6, 7, 8, 9 = 5개
M보다 크므로 left = mid+1 = 13

4. left = 13, right = 16, mid = (13+16)/2 = 14
블루레이 개수 : 1~5, 6~7, 8, 9 = 4개
M보다 크므로 left = mid+1 = 15

5. left = 15, right = 16, mid = (15+16)/2 = 15
블루레이 개수 : 1~5, 6~7, 8, 9 = 4개
M보다 크므로 left = mid+1 = 16

6. left = 16, right = 16, mid = (16+16)/2 = 16
블루레이 개수 : 1~5, 6~7, 8, 9 = 4개
M보다 크므로 left = mid+1 = 17 

끝
= M보다 작거나 같은 최소 길이는 17이다. 

 

나의 풀이

---

1차

#include <iostream>
#include <vector>
#include <algorithm>
typedef long long ll;

using namespace std;

ll solve(int N, int M, vector<int> lectures) {
    

    // 블루레이 크기 이분탐색으로 구하기
    // left = 강의 길이 중 최댓값
    ll left = *max_element(lectures.begin(), lectures.end());
    // right = 모든 강의길이 합
    ll right = 0;
    for(int i : lectures) {
        right += i;
    }

    if (N == M) {
        return left;
    }

    ll answer = right;
    while(left <= right) {
        ll mid = (left + right) / 2;

        // check 
        // 강의 돌면서 더하기 
        ll blue_ray_count = 1;
        ll sum = 0;
        for(int i : lectures) {
            
            // 초과되면 개수 +1
            if (sum+i > mid) {
                sum = 0;
                blue_ray_count++;
            }

            sum += i;

            if (blue_ray_count > M) 
                break;
        }
        
        if (blue_ray_count > M) {
            left = mid + 1;
        } else {
            if (blue_ray_count == M) {
                answer = min(answer, mid);
            }

            right = mid - 1;
        }
    }
    
    return answer;
}

int main() {

    int N, M;
    vector<int> lectures;

    // input
    cin >> N >> M;

    int lecture;
    for(int i=0; i<N; i++) {
        cin >> lecture;
        lectures.push_back(lecture);
    }

    cout << solve(N, M, lectures);

    return 0;
}

 

결과 : 50%에서 틀렸습니다

블루레이 갯수가 M개 되었을 때에만 최소값 비교 후 바꿔주었는데,

(M개보다 많거나 적으면 그냥 start, end 범위만 바꿔줌)

블루레이 갯수가 M개 미만일때도 최소값 비교 후 바꿔주어야합니다.

꼭 M개를 정확히 맞추지 않아도 되는 것 같아요

 

https://www.acmicpc.net/board/view/143842

 

 

위의 질문 게시판을 보고, 블루레이 갯수가 M개 미만일때도 정답을 갱신하도록 변경하였다.

 

---

2차

#include <iostream>
#include <vector>
#include <algorithm>
typedef long long ll;

using namespace std;

ll solve(int N, int M, vector<int> lectures) {
    

    // 블루레이 크기 이분탐색으로 구하기
    // left = 강의 길이 중 최대? 
    ll left = *max_element(lectures.begin(), lectures.end());
    // right = 모든 강의길이 합
    ll right = 0;
    for(int i : lectures) {
        right += i;
    }

    ll answer = right;
    while(left <= right) {
        ll mid = (left + right) / 2;

        // check 
        // 강의 돌면서 더하기 
        ll blue_ray_count = 1;
        ll sum = 0;
        for(int i : lectures) {
            
            // 초과되면 개수 +1
            if (sum+i > mid) {
                sum = 0;
                blue_ray_count++;
            }

            sum += i;

            if (blue_ray_count > M) 
                break;
        }
        
        if (blue_ray_count > M) {
            left = mid + 1;
        } else {
            answer = min(answer, mid);
            right = mid - 1;
        }
    }
    
    return answer;
}

int main() {

    int N, M;
    vector<int> lectures;

    // input
    cin >> N >> M;

    int lecture;
    for(int i=0; i<N; i++) {
        cin >> lecture;
        lectures.push_back(lecture);
    }
    
    cout << solve(N, M, lectures);

    return 0;
}

 

결과 : 정답

 

정리

---

 

제출하기 전 다양한 케이스들을 최대한 생각해보고, 제출하려 하고 있다. 

훨씬 효과가 좋은듯!