글 읽기 - 오버플로우를 방지하기위해 어떻게 고쳐야 할까요?

xorms86 3년 전 0

문제에서 최대 입력값이 4,294,967,295 이고, unsigned int의 최댓값도 4,294,967,295 이여서 l, r, result를 unsigned int로 선언하였습니다.

입력으로 4,294,967,294까지는 92681이라는 출력값이 잘나오는데 4,294,967,295를 넣으면 제대로된 답이 안나오더라고요.

12번줄인 (l+r), 즉 ( 1+4,294,967,295)로 인해 오버플로우가 발생하는것 까지는 알아냈는데 코드를 어떻게 수정해야할지를 모르겠습니다.

l, r, result의 자료형은 unsigned int로 그대로 두면서 12,13번줄에서 오버플로우가 안나도록 하려면 어떻게 형변환을 해줘야 할까요?

ex) (long long)(l+r)/2; -> 여전히 답이 안나오는 코드

#include<iostream>
using namespace std;

int main() {
	unsigned int  n;
	cin >> n;

	unsigned int l = 1;
	unsigned int r = n;  //4,294,967,295
	unsigned int result = 0;
	while (l <= r) {
		long long mid = (l + r) / 2; //오버플로우 발생?
		if (mid *(mid + 1) / 2 <= n) {
			result = mid;
			l = mid + 1;
		}
		else {
			r = mid - 1;
		}
	}
	cout << result;
}

39dll 3년 전 1

unsigned int끼리의 연산 결과 type은 unsigned int입니다. 그렇기 때문에 (long long)(l+r)/2과 같이 쓰면 l+r인 시점부터 이미 오버플로우가 납니다.

아래와 같이 쓰면 됩니다.

//Wrong
(long long)(l + r) / 2

//Right
((long long)l + r) / 2

xorms86 3년 전 0

@39dll 한틱차이가 엄청난 차이군요.. 감사합니다

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

문제

문제

출처

ICPC

오버플로우를 방지하기위해 어떻게 고쳐야 할까요?

xorms86 3년 전 0

39dll 3년 전 1

xorms86 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말