43번 뮤직비디오 문제 테스트케이스 4번을 만족 못합니다.

안녕하세요 문제를 풀다가 제 코드에서 어느 부분이 틀린 건지 도무지 모르겠어서 글을 쓰게 되었습니다..
혹시 괜찮으시다면 제 코드 상에서 논리적인 오류가 있는지 확인해주실 수 있으신가요?

테스트케이스 4번만 만족을 못시키고 있습니다.. 감사합니다.

#include <iostream>
#include <stdio.h>
#include <string>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);

	int n, m;
	cin >> n >> m;
	vector<int> table(n);
	int sum = 0;

	for (int i = 0; i < n; i++) {
		cin >> table[i];
		sum += table[i];
	}

	int lt = 1, rt = sum, mid = 0;
	int last = 1001;
	while (lt <= rt) {
		mid = (lt + rt) / 2;

		int cnt = 1;
		int sum = 0;
		for (int i = 0; i < n; i++) {
			if (sum + table[i] > mid) {
				cnt++;
				sum = table[i];
			}
			else if (sum + table[i] == mid) {
				cnt++;
				sum = 0;
			}
			else sum += table[i];
		}
		if (sum == 0) cnt--;

		if (cnt == m) {
			if (last > m) {
				last = m;
				rt = mid - 1;
			}
			else break;
		}
		else if (cnt < m) rt = mid - 1;
		else lt = mid + 1;
	}

	cout << mid << "\n";

	return 0;
}

안녕하세요, 인프런 AI 인턴입니다.

youch1127님의 코드를 살펴보았습니다. 코드 상의 로직은 대체적으로 올바른 방향을 가리키고 있습니다만, last 변수의 사용 목적과 관리에 있어서 논리적인 오류가 있는 것 같습니다.

이 문제의 핵심은 이분 탐색을 통해 최소의 DVD 용량(최대값 중 최소값)을 찾는 것입니다. 그렇기 때문에, DVD 최소 용량을 찾기 위해 각 시도마다 cnt(DVD 갯수)와 m(요구되는 DVD 개수)을 비교하여 이분 탐색의 범위를 좁혀나가야 합니다.

문제는 last 변수에 있습니다. 이 변수는 코드 내에서 실제로 용도가 모호하며, 정확한 비교를 위해 현재 로직에서는 불필요합니다. last 변수가 담고자 하는 목적이 DVD 개수의 최소값을 찾는 것이라 해도, 현재의 구현 방식에서는 적절히 활용되지 않고 있습니다. 이분 탐색 과정에서 cnt == m일 때 last > m 조건은 사실상 의미가 없으며, 이 조건문으로 인해 불필요한 비교만 하고 있습니다.

last 변수 대신 조건을 만족하는 경우(mid 값이 조건에 부합하는 경우), 최소 값을 갱신하는 방법으로 접근해야 합니다. 따라서, last 변수와 해당 조건문을 제거하는 것이 좋습니다. 대신, cnt == m인 경우에 rt = mid - 1로 설정하여 이분 탐색을 계속 진행하되, 그 과정에서 가능한 최소 mid 값을 결과로 출력하도록 로직을 조정해야 합니다.

따라서, 아래와 같이 코드를 수정할 수 있습니다.

if (cnt <= m) {
	rt = mid - 1;
}
else {
	lt = mid + 1;
}

수정 후, cnt == m 조건에서 결과를 출력하던 방식을 cnt <= m로 변경하는 것이 핵심입니다. 이렇게 조정하면, 요구하는 DVD 개수(m)보다 같거나 작은 경우에만 용량의 최대값을 감소시키면서 최적의 해를 찾을 수 있습니다.

이에 따라, 조건을 만족하는 최소 mid 값을 찾기 위해 이분 탐색의 왼쪽 범위를 좁히는 방식으로 로직을 개선하는 것이 좋겠습니다.

인프런 커뮤니티 질문&답변