글 읽기 - 코드에 주석 달았습니다! min을 기준으로 탐색하면 안되는 이유가 궁금합니다ㅠㅠ

croco1997 2년 전 0

랜선 자르기 문제에서 max값이 아닌 min값을 기준으로 찾으면 "틀렸습니다"가 뜨는 이유가 궁금합니다.

아래의 코드에서 min이 아닌 max값을 기준으로 작성했더니 "맞았습니다"가 떴습니다.

제 생각에는 두 코드 모두 문제 없다고 생각하는데, min값을 기준으로 하면 문제가 되는 이유가 궁금합니다.

// 최소 값을 기준으로 탐색한 코드 ( 틀렸습니다 )

#include <iostream>
#include <climits>

using namespace std;

long long K[10000];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int inputK, inputN;
	// 1cm의 단위로 자른다면, count가 21억을 초과하는 수가 등장할 수 있으므로, 자료형은 long long이다.
	long long count = 0;
	// long long 자료형이 갖는 최대의 숫자를 표현한다.
	long long min = LLONG_MAX;

	cin >> inputK >> inputN;

	for (int i = 0; i < inputK; i++) {
		cin >> K[i];

		// 최소 값을 구한다.
		if (K[i] < min)
			min = K[i];
	}

	// 랜선을 자르는 길이는 0이어서는 안된다.
	// 따라서 left는 1로 설정한다.
	long long left = 1;
	long long right = min;
	// 가장 작은 숫자의 길이를 기준으로, 나머지 길이들을 몇 개로 자를 수 있는지 확인한다.
	long long mid = min;

	while (left <= right) {
		count = 0;

		for (int i = 0; i < inputK; i++) {
			// 가장 작은 숫자의 길이를 기준으로, 나머지 길이들을 몇 개로 자를 수 있는지 확인한다.
			count += (K[i] / mid);
		}

		// count가 inputN보다 크다는 것은 케이블을 더 긴 길이로 잘라도 된다는 것을 의미한다.
		// count와 inputN이 같아도, 더 길게 자를 수 있는지 확인해봐야 하므로 조건에 = 도 추가한다.
		if (count >= inputN) {
			left = mid + 1;
		}

		if (count < inputN) {
			right = mid - 1;
		}

		// 중간 값을 다시 설정한다.
		mid = (left + right) / 2;
	}

	cout << mid;
}



// 최대 값을 기준으로 탐색한 코드 ( 맞았습니다 )

#include <iostream>

using namespace std;

long long K[10000];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int inputK, inputN;
	// 1cm의 단위로 자른다면, count가 21억을 초과하는 수가 등장할 수 있으므로, 자료형은 long long이다.
	long long count = 0;
	long long max = 0;

	cin >> inputK >> inputN;

	for (int i = 0; i < inputK; i++) {
		cin >> K[i];

		if (K[i] > max)
			max = K[i];
	}

	// 자르는 길이는 0이어서는 안된다.
	// 따라서 left는 1로 설정한다.
	long long left = 1;
	long long right = max;
	// 가장 큰 숫자의 길이를 기준으로, 일단 mid 값을 설정한다.
	long long mid = max;

	while (left <= right) {
		count = 0;

		for (int i = 0; i < inputK; i++) {
			// 중간 값 길이를 기준으로, 나머지 길이들을 몇 개로 자를 수 있는지 확인한다.
			count += (K[i] / mid);
		}

		// count가 inputN보다 크다는 것은 케이블을 더 긴 길이로 잘라도 된다는 것을 의미한다.
		// count와 inputN이 같아도, 더 길게 자를 수 있는지 확인해봐야 하므로 조건에 = 도 추가한다.
		if (count >= inputN) {
			left = mid + 1;
		}

		if (count < inputN) {
			right = mid - 1;
		}
		
		mid = (left + right) / 2;
	}

	cout << mid;
}

zenith82114 2년 전 2

최솟값이 필요가 없을 수도 있습니다.

2 10
2
100

jhp1276 2년 전 1

저도 똑같은 min써서 계속 틀렸습니다가 나왔다가 max로 바꿔서 정답입니다가 나왔어요~!

곰곰히 생각을 해보니

2 2

2147483647

min을 쓰면 1, max를 쓰면 1073741823이 나오는데

생각해보니 똑같은 길이로 2개만 있으면 되니까 1짜리는 안쓰고 2번 째 2147483647로 반 자르면 되더라구요

그래서 틀렸습니다가 나왔네요!

위에 분 예시도

min쓰면 2가 정답으로 나오고 max로 하면 10이 나오네요!

정말 큰 도움이 됐습니다! 감사합니다 ^^

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

문제

문제

출처

ICPC

코드에 주석 달았습니다! min을 기준으로 탐색하면 안되는 이유가 궁금합니다ㅠㅠ

croco1997 2년 전 0

zenith82114 2년 전 2

jhp1276 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말