글 읽기 - 1654 c언어 틀린 이유를 모르겠습니다 ㅜ

khaerim41 2년 전 0

제가 테스트 해본 값들은 모두 제대로 나오는 데 제출 해보니 틀리다고 나옵니다.

어느 부분이 틀린 걸까요 ? 이진 탐색으로만 풀어야 되는 건가요 ?

#include <stdio.h>
int K,N; 

int cal(int line[],int length){
	int sum=0;
	for(int i=0; i<K; i++) sum += line[i] / length;
	return sum;
}
int main(){
	scanf("%d %d",&K, &N);
	int line[K],sum =0;
	for(int i =0; i<K; i++) { scanf("%d",&line[i]); sum+= line[i]; }
	int length = sum / N, result; 
	while (1){
		if(cal(line,length) >= N) { printf("%d",length); break; }
		length--;
	}
}

cakelemon 2년 전 1

sum 을 구할 때 오버플로우가 발생합니다.

문제 조건에 따르면 입력될 수 있는 랜선의 최대 길이는 2147483647 = 2³¹ - 1 입니다.

이는, 저정도로 긴 랜선 2 개만 입력이 되어도, sum 값이 음수가 되어 버릴 수 있음을 의미합니다.

int 대신 long long 등의 타입을 활용하는 게 좋을 것 같네요.

* 다만 long long 으로 변환해서 문제가 더 이상 틀리지 않게 되더라도, sum / N 은 최대 2147483647 이라는 큰 값이 될 수 있으므로

시간초과가 발생할 가능성이 높습니다.

khaerim41 2년 전 0

그렇군요 ㅠㅠㅠㅠㅠ 발견해주셔서 감사합니다

이진 탐색으로 할 수 밖에 없겠네요 ! 다시 구현 해보겠습니당

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

문제

문제

출처

ICPC

1654 c언어 틀린 이유를 모르겠습니다 ㅜ

khaerim41 2년 전 0

cakelemon 2년 전 1

khaerim41 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말