[알고리즘] 백준 2343번: 기타레슨 (C++), 다른 사람 코드는 귀한 교과서

 이번 문제가 어려웠던 이유는 무엇을 이분 탐색해야 하는지도 정확히 파악하고 있고, 논리까지 짰었지만 센스(?)가 없어서 풀지 못하던 문제이다.

(알고리즘은 이분 탐색을 사용했기에 이분 탐색 카테고리에 넣어둔다.)

 

우선 블루레이의 크기를 탐색하기 때문에 1을 low로 두고, 모든 강의 길이의 합을 high로 두고,

나오게 된 mid에 맞춰서 sum변수를 선언하고, 강의의 길이를 하나씩 더해가며 sum이 mid를 넘을 때마다 블루레이 하나 더 써야겠다 라는 논리로 접근하면 된다.

 

이번 문제에서 해결하지 못하는 포인트가 2가지였다.

1. sum이 mid를 넘어갈 때, sum을 0으로 초기화해버리면 넘어갈 때 순간의 원소(강의의 길이)는 어떻게 해결하나
2. mid로써 주어진 길이가 7이라고 치면 한 강의의 길이가 8일 땐 어떻게 처리하나

우선 해결하기 전의 코드를 가져왔다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	int n, m;
	cin >> n >> m;
	vector<int> arr;
	int high = 0;

	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		arr.push_back(a);
		high += a; // 모든 강의가 하나의 블루레이에 들어갈 때 제일 클 거 같음 >> high가 될 수 있겠다 생각함
	}

	int low = 1;
	// low, high 정의 끝

	int answer = 0;

	while (low <= high) {
		int mid = (low + high) / 2;
		int cnt = 0; // 사용되는 블루레이 개수 카운트
		int sum = 0;
		vector<int> sums;// 나온 블루레이의 길이들을 담는 배열 >> 나중에 최대값을 구하기 위해
		int arrCnt = 0;

		for (int i = 0; i < arr.size(); i++) {
			if (i != 0) {// i - 1이 0에서 발생하면 범위 오류남
				if (sum > mid) { // 주어진 mid(블루레이의 길이)보다 클 때
					sum -= arr[i - 1];
					sums.push_back(sum);// 블루레이 하나 끝
					cnt++; // 블루레이 하나 컷
					sum = 0; // sum 초기화
					arrCnt = 0;
				}
				// else라면 그냥 계속하면 될 듯
			}
			sum += arr[i];

			arrCnt++;

			if (arrCnt == 1 && sum > mid) {// 하나의 강의 길이가 mid보다 크다면 그 자체로 설정오류다. >> sum, arrCnt 초기화하고 pass
											// 일단 sums에 담아봐야할 거 같다.
				sums.push_back(sum);
				sum = 0;
				arrCnt = 0;
			}
		}

		for (int i = 0; i < sums.size(); i++) {
			cout << sums[i] << '\n';
		}
		cout << mid << ' ' << low << ' ' << high << '\n';

		if (sums.size() < m) {
			high = mid - 1;
		}
		else {
			low = mid + 1;
			answer = mid;
		}
	}

	cout << answer;
	return 0;
}

while문 안에 저 복잡한 들여 쓰기와 여러 변수 선언은 지금 봐서 사실 해석하기도 어렵다.

포인트 1번을 해결하기 위해서 저렇게 했었는데

이 분의 코드를 참고했다.

(구글링 하다 보면 이 분 코드를 많이 보게 되는 거 같다. 구독해놔야지😁😁)

https://jaimemin.tistory.com/1130

백준 2343번 기타 레슨

 

타고 들어가서 이 분의 코드는 따로 함수를 선언하셔서 while 안에서 함수를 콜 하시고, 조건문으로 가는 방식의 코드를 짜셨다.

하지만, 내가 얻고자 하는 것은 1번 포인트였기에 이 부분을 참고했다.

정말 간단했다.

애초에 sum이 mid를 넘기면 sum을 0으로 초기화하는 것이 아니라 mid를 넘어가게 한 그 원소로 sum에 할당해주면 되는 간단한 방법이었다.

 

이해하자마자 와 왜 이 생각을 못 했지 (1분 동안 멍 때림)

 

2번 포인트 또한 이 분이 작성한 함수에서 이해할 수 있었다.

내가 작성한 코드로 보면

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
	int n, m;
	cin >> n >> m;

	vector<int> arr;
    int high = 0;
	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		arr.push_back(a);
        high += a;
	}

    int low = 1;
    int answer = 0;

    while (low <= high) {
        int mid = (low + high) / 2;
        int sum = 0;
        int cnt = 0; // 블루레이 몇 개 쓰는지 확인용
        bool wrongAns = false;

        for (int i = 0; i < arr.size(); i++) {
            if (arr[i] > mid) {
                //현재의 mid는 답이 아니라는 뜻 >> 이 부분도 키포인트
                wrongAns = true;
                break;
            }

            sum += arr[i];

            if (sum > mid) {
                cnt++;
                sum = arr[i]; // 이 부분이 진짜 키포인트였다.
            }
        }
        cnt++; // 마지막 if문에서 조건만 통과하고 남은 원소들의 합 또한 블루레이를 사용한다.

        //출력확인용 //cout << cnt << ' ' << mid << ' ' << high << ' ' << low << ' ' << wrongAns << '\n';

        if (wrongAns) {
            low = mid + 1;
            continue;
        }

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

    cout << answer;
    return 0;
}

bool형 변수로 wrongAns라 선언하고 어떤 한 원소가 mid보다 클 때 wrongAns를 true로 할당해주고, for문을 뛰쳐나와 if 조건문을 만나게 했다.

그리고, 조건문 안에 low = mid + 1은 어떤 한 원소도 블루레이에 포함되어야 하기에 mid를 더 크게 만들어야 한다는 생각에 저렇게 작성해주었다.

 

---

결론

sum을 0이 아닌 원소로 초기화 한 센스... 이렇게 또 배웁니다.