글 읽기 - 랜선자르기 이진탐색에 대해서 질문 드립니다.

thereon42 6년 전 0

안녕하세요

랜선자르기 문제를 풀다가 이해가 가지 않은 점이 생겨서 이렇게 질문 드립니다.

아래 코드를 보면 이진 탐색을 하면서, sum 이 잘라진 랜선의 갯수를 의미하는데요, 이 랜선의 갯수가 주어진 m의 갯수에 대해서 크냐, 작냐에 대해서 시작 값과 끝값중 어느값을 가운데로 옮길 것일 지를 결정하는데요,

제가 생각하기에는 주어진 문제처럼 sum 값이 m이랑 같은 경우에만 답이 최대값이 맞는지를 확인하면 될꺼라고 생각했는데 아래 코드를 제출하면 틀렸습니다 가 나옵니다.

그 후 sum이 같거나, m 보다 큰 경우에 답의 최대값이 맞는지 분류를 나눴더니 정답으로 처리가 되더군요.

왜 이렇게 되는지 이해가 잘 되지 않아서 질문드립니다.ㄷ

#include <iostream>
#include <algorithm>

using namespace std;

long long lan[10001];

long long search(long long start,long long end, int m, int n)
{

	long long ans = 0;
	while (start <= end)
	{
		
		long long mid = (start + end) / 2;
		long long sum = 0;
		for (int i = 0; i < n; i++)
		{
			sum += lan[i] / mid;
		}

		if (sum == m) // 이렇게 sum ==m인 경우를 합쳐서 생각하면 틀렸습니다가 나옵니다.
		{
			if (ans < mid)
				ans = mid;
			start = mid +1;
		}
		else if (sum < m)
		{

			end = mid-1;
		} 
		else if (sum > m)
		{
			start = mid+1;
		}
	}
	return ans;
}

int main(void)
{
	int n, m;
	cin >> n >> m;
	long long max = 0;
	for (int i = 0; i < n; i++)
	{
		cin >> lan[i];
		if (max < lan[i])
			max = lan[i];
	}

	long long result = search(0,max , m, n);

	cout << result;
}

jh05013 6년 전 0

sum이 정확히 m일 필요는 없습니다. m개를 넘으면 그 만큼 버려서 m개를 맞출 수 있습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

랜선자르기 이진탐색에 대해서 질문 드립니다.

thereon42 6년 전 0

jh05013 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말