글 읽기 - int 범위 벗어나서 그런건지 어떻게 고쳐야할지 모르겠네요

car584 1년 전 0

코드가 맞는지는 모르겠으나 반례들을 찾아보니 다른건 맞는것같은데 int의 범위를 벗어났을 경우 틀리길래 long long으로 바꾸어주었으나 범위를 벗어나게 입력할경우 프로그램이 멈춰버리네요. 코딩 공부좀 더해야겠습니다... 해결법을 부탁드려도될까요?

#include <cstdio>
#include<stdio.h>
#include<stdlib.h>

int main(void) {
	int K, N;
	long long L = 1; //길이

	scanf("%d %d", &K, &N);

	long long* s = (long long*)malloc(sizeof(long long) * K);
	long long c = 0; //갯수

	for (int i = 0; i < K; i++) {
		scanf("%lld", &s[i]);
	}

	while (true) {
		c = 0;
		for (int j = 0; j < K; j++) {
			c += s[j] / L;
		}

		if (c < N) {
			break;
		}
		L++;
	}

	printf("%lld\n", L-1);


}

bamgoesn 1년 전 1

int를 사용할 경우 오버플로우가 있을 건 맞으며, 그걸 long long으로 고친 건 잘 하셨습니다.

하지만 위 코드는 지금 정답이 L일 때 루프를 L번 돌면서 매 루프마다 모든 랜선을 순회하며 c의 값을 계산하므로 시간복잡도가 O(NL)입니다. L은 최대 약 10^9, N은 최대 10^6이므로, O(NL)은 시간이 너무 오래 걸립니다.

매개변수 탐색이라는 걸 검색해보세요.

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

문제

문제

출처

ICPC

int 범위 벗어나서 그런건지 어떻게 고쳐야할지 모르겠네요

car584 1년 전 0

bamgoesn 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말