글 읽기 - 이 문제 왜 int로는 안되는지 궁금합니다.

kangsy763 4년 전 0

랜선 길이가 2^31-1 이면 int 범위여서 int 로 두고 풀었는데 틀렸다고 뜨길레 long long 고쳤더니 맞았는데요..

이해가 잘 안갑니다. int로도 가능하지 않나요 ? 정작 right 값은 int_max로 두고 풀었는데 말이죠..

그래서 한 두개씩 long long 으로 바꿔서 해봤는데도 안되네요? 제일 이상한건 left만 long long 하고 나머지 int를 두면 시간초과가 나온다는 것이...

왜 long long 으로 해야하나요 ? left right이 둘 다 int_max 라 하더라도 pivot은 /2 하니깐 결국 int범위에 딱 들어올 텐데 말이죠 딱 int_max일 때에 left 값이 +1 이 되면 넘어가니깐 long long 바꿔봤는데 이것도 안되니깐 정말 모르겠습니다.

#include <stdio.h>
#include <vector>
#include <limits.h>
using namespace std;

int main() {
	long long k, n, num, result = 0;
	long long left, right, pivot, max = 0;
	vector<int> vv;
	scanf("%lld %lld", &k, &n);
	for (int i = 0; i < k; i++) {
		scanf("%lld", &num);
		vv.push_back(num);
	}
	left = 0, right = INT_MAX;
	while (left <= right) {
		result = 0;
		pivot = (left + right) / 2;
		for (int i = 0; i < k; i++) {
			result += vv[i] / pivot;
		}
		if (result >= n) {
			left = pivot + 1;
			if (pivot > max) max = pivot;
		}
		else {
			right = pivot - 1;
		}
	}
	printf("%lld", max);
	return 0;
}

shiftpsh 4년 전 4

랜선 하나는 int 안에 들어오지만 랜선이 10,000개이고 이걸 다 1cm짜리로 자른다고 치면 10,000 × (2³¹ − 1)조각이 나오므로 안됩니다.

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

문제

문제

출처

ICPC

이 문제 왜 int로는 안되는지 궁금합니다.

kangsy763 4년 전 0

shiftpsh 4년 전 4

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말