글 읽기 - 2805 나무자르기 질문

qkrclrl701 5년 전 0

잘라낸 나무의 길이가 int 범위를 초과하는 경우를 고려해서 cur_len < 0 (오버플로우가 발생) 하면 M보다 잘라낸 나무의 길이가 더 크거나 같게 되고, max값이 현재 mid보다 크거나 같아야 한다는 논리로 코드를 작성하였는데요, cur_len을 long long int type으로 바꾸면 맞는 결과가 나오는데, 왜 주어진 코드가 제대로 답을 못 구하는건지 이해가 안가네요.. 어느 부분에서 문제가 있는 걸까요?

#include <stdio.h>

int a[1000001];

int main(){
	int N, M, i, max = -1;
	scanf("%d %d", &N, &M);
	for(i = 0; i < N; i++){
		scanf("%d", &a[i]);
	}
	int left = 0, right = 1000000000, mid = (right + left + 1) / 2;
	while(left <= right){
		int cur_len = 0;
		for(i = 0; i < N; i++){
			if(a[i] > mid){
				cur_len += a[i] - mid;
			}
			if(cur_len < 0){
				break;
			}
		}

		if(cur_len < 0 || cur_len >= M){
			if(max < mid){
				max = mid;
			}
			left = mid + 1;
			mid = (right + left + 1) / 2;
		}
		else if(cur_len < M){
			right = mid - 1;
			mid = (right + left + 1) / 2;
		}
	}
	printf("%d", max);
} 

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

문제

문제

출처

ICPC

2805 나무자르기 질문

qkrclrl701 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말