글 읽기 - 2805 C 고수님들 확인 부탁드려요ㅠㅠ / long long, int

hwangsu98 1년 전 0

43번 line 변수 sum 의 type 을 long long int 에서 int 로 바꿔도 47 line if 에서 걸리기 때문에,

int 와 long long int 의 경우 걸러지는 게 동일하다고 생각되는데,

long long 을 떼면 70퍼 쯤에서 틀리고, 붙이면 통과가 되네요..

혹시 설명을 부탁드릴 수 있을까요..ㅠㅠㅠㅠㅠ 알고 싶습니다 이유를..

#define M_LIMIT 2000000000

int trees[1000000] = {};

int cutting(int [], int, int);

main() {
	int n, m, i, min = 0, max = -1, mid, temp;
	scanf("%d%d", &n, &m);
	
	for (i = 0; i < n; i++) {
		scanf("%d", &trees[i]);
		if (trees[i] > max)
			max = trees[i];
	}
	
	int cut_height;
	while(1) {
		mid = (max + min) / 2;
		
		if (mid == min) {
			if (cutting(trees, n, mid + 1) >= m) {
				cut_height = mid + 1;
				break;
			} else {
				cut_height = mid;
				break;
			}
		}
		temp = cutting(trees, n, mid);
		
		if (temp == m) {
			cut_height = mid;
			break;
		} else if (temp < m)
			max = mid;
		else min = mid;
	}
	printf("%d", cut_height);
}

int cutting(int tree_arr[], int size, int cut) {
	long long int sum = 0;
	for (int i = 0; i < size; i++) {
		if (tree_arr[i] > cut)
			sum += tree_arr[i] - cut;
		if (sum > M_LIMIT || sum < 0)
			return M_LIMIT + 1;						// 자른 sum 이 M 범위(= 2,000,000,000) 보다 크면,
    }
	return sum;										// 절단기 높이 올리기 위해 2,000,000,001 리턴, 
}

tori1753 1년 전 0

47번 라인으로 가기전에 46번 라인의 sum에서 오버플로가 발생했을 상황이 문제가 될 것 같아 보입니다.

hwangsu98 1년 전 0

일단 답변 감사합니다.

근데, 오버플로가 발생하면 음수가 되기에 무조건 sum < 0 에서 걸러지지 않나요?

tree_arr[i] - cut 이 최대 10억인데, sum 이 최대 20억일때를 생각하면, if (sum > M_LIMIT || sum < 0) 에서 무조건 걸러진다고 생각하는데,

혹시 제가 무엇을 잘못 알고 있을까요...

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

문제

문제

출처

ICPC

2805 C 고수님들 확인 부탁드려요ㅠㅠ / long long, int

hwangsu98 1년 전 0

tori1753 1년 전 0

hwangsu98 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말