글 읽기 - 코드 질문입니다.

bfryn1004 5년 전 0

hi값을 배열의 최댓값 + 1 로 잡았을 때(1번 코드)는 성공합니다.

그런데 hi값을 100001 / 문제에서 내준 최대 예산 + 1(2번 코드) 로 잡으면 실패합니다.

이유가 무엇인가요?

                            1번
#include <cstdio>
using namespace std;

int arr[10000];

int main() {
	int number, goal, hi = -1;
	long long tot = 0;
	scanf("%d", &number);
	for (int i = 0; i < number; i++) {
		scanf("%d", &arr[i]);
		if (arr[i] > hi) hi = arr[i];
	}
	scanf("%d", &goal);
	int lo = 0;					
	hi++;
	while (lo + 1 < hi) {		
		tot = 0;
		int mid = (lo + hi) / 2; 
		for (int i = 0; i < number; i++) {
			if (arr[i] >= mid) tot += mid;
			else tot += arr[i];
		}
		if (tot > goal) hi = mid;
		else lo = mid;
	}
	printf("%d", lo);
}
                            2번
#include <cstdio>
#include <vector>
using namespace std;

vector <int> list;

int main() {
	int numberOfCity, maxBudget;
	scanf("%d", &numberOfCity);
	list = vector <int>(numberOfCity, 0);
	for (int i = 0; i < numberOfCity; i++)
		scanf("%d", &list[i]);
	scanf("%d", &maxBudget);

	int lo = 0, hi = 1000000001;
	while (lo + 1 < hi) {
		int mid = (lo + hi) / 2;
		long long tmp = 0;
		for (int i = 0; i < numberOfCity; i++) {
			if (list[i] < mid) tmp += list[i];
			else tmp += mid;
		}
		if (tmp <= maxBudget) lo = mid;			
		else hi = mid;							
	}
	printf("%d", lo);
}

djm03178 5년 전 1

전체 예산 요청 중 최댓값으로 설정해도 그 합이 예산총액에 못 미칠 수 있습니다. 이럴 경우 계속해서 lo가 증가하게 되지만 총합이 늘어나지는 못하므로 lo가 hi까지 가게 됩니다.

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

문제

문제

출처

ICPC

코드 질문입니다.

bfryn1004 5년 전 0

djm03178 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말