글 읽기 - 틀린 부분 도움 부탁드립니다~

mariocrat 4년 전 0

이분 탐색으로 가장 짧은 길이는 1로,

가장 긴 길이는 가진 케이블 중에 가장 짧은 min으로 설정했습니다.

중간 값을 기준으로 최대 길이를 찾아가도록 구현하고자 했는데,

결과값이 틀렸다고 나오는데 반례를 찾지 못해서 원인을 못 찾고 있는데

고수님들 도움 부탁드립니다~!

#include <iostream>
using namespace std;

int main() {
	int N, K;
	cin >> K >> N;

	int cable[10001];
	int min=1000000;

	for (int i=0; i < K; i++) {
		cin >> cable[i];
		if (min > cable[i])	min = cable[i];
	}

	long long low = 1, high = min;
	while (low+1 < high) {
		long long mid = (low + high) / 2;
		long long tmp = 0;

		for (int i = 0; i < K; i++) {
			tmp += cable[i] / mid;
		}

		if (tmp >= N) low=mid;
		else high=mid;
	}

	cout << low;
	return 0;
}

qwq94 4년 전 0

코드는 해석 안했구 저도 같은 이유로 고민하다가 나온 반례인데 참고하세요

3 3

Answer = 5

Output = 2

최대 길이는 주어진 랜선 길이 중에 max로 잡아야해요! 그렇게 안하면 해당 길이를 사용하지 않는 경우 오답이 나옵니당

2 2

Answer = 3

Output = 2

이 경우도 다르게 나오네요

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

문제

문제

출처

ICPC

틀린 부분 도움 부탁드립니다~

mariocrat 4년 전 0

qwq94 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말