글 읽기 - c언어) 반례를 모르겠습니다.

qkre 2년 전 0

예제는 전부 맞는데, 오버플로우가 발생해서 실패하는 것인지 궁금하네요. 오버플로우가 발생할 경우 정수형을 바꿔 주어야 할 지 궁금합니다.

#include <stdio.h>

int main(){
	
	int a, b ,c;
	scanf("%d %d %d", &a, &b, &c);
	
	int temp = c;
	int sum = a + b;
	int count = 1;
	while(1) {
		if(a < 0 || b < 0 || c < 0){
			count = -1;
			break;
		}
			
		if(b > c){
			count = -1;
			break;
		}
		
		if(sum < c)
			break;
		
		sum += b;
		c += temp;
		count++;
			
	}
	
	printf("%d", count);
	
	return 0;
}

nahwasa 2년 전 1

네 오버플로우가 발생해서 실패합니다. 3번째 예제가 통과가 안되셨을텐데요?!

문제에 제시된 3번째 예제에서 21억1번에 걸쳐 sum+=b가 일어나야하는데

이미 int형 범위는 넘어섰죠.

오버플로우를 대비해서 정수형을 바꿔줘야 하는지에 대해서는,

사실 이것도 답은 아닙니다.

이 문제는 오버플로우를 내지 않고 풀 방법이 존재하기 때문이죠.

매번 더해보는 위 코드의 Brute Force 형식으로는, 최대 약 21억번의 연산이 필요하므로 시간초과가 나게 됩니다.

애초에 다른 로직을 생각해보시는게 좋겠습니다.

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

문제

문제

출처

ICPC

c언어) 반례를 모르겠습니다.

qkre 2년 전 0

nahwasa 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말