글 읽기 - 1654 랜선자르기 시간초과 질문

zeikar 8년 전 0

모든 길이를 더한 후 N으로 나눈 값부터 모두 탐색하게 짰는데 역시나 시간초과가 뜨네요 ㅠㅠ

다른 방법으로 접근해야할거 같은데 감이 안오네요...

#include <iostream>
using namespace std;

int main()
{
	long long K, N, sum = 0, *lan, len;

	cin >> K >> N;

	lan = new long long[K];

	for(int i = 0; i < K; ++i)
	{
        cin >> lan[i];
		sum += lan[i];
		// 지금까지 총 길이 sum
	}
	// 입력받음

	for(len = sum / N; len > 0; --len)
	{
		// 모든 길이 탐색
		int count = 0;

		for(int i = 0; i < K; ++i)
		{
			count += lan[i] / len;
		}

		// 자른 개수 count

		if(count >= N)
		{
			break;
		}
		// 충분한 조각이 나오면 break
	}

	cout << len << endl;

	delete[] lan;
}

mastojun 8년 전 5

접근은 잘 하신거 같은데 탐색방법만 좀더 효율적으로 바꾸시면 될듯 합니다.

일단, 입력으로 주어지는 랜선의 길이의 입력범위는 주어지지 않았으므로 sum += lan[i]의 경우 overflow가 발생할 가능성이 있고요.

길이가 k 인 랜선으로 자를 때 그 갯수가 N개 이하라면 k 이상의 수는 정답 후보에서 제외됩니다.
길이가 k 인 랜선으로 자를 때 그 갯수가 N개 이상이라면 k 이상의 수 중에 답이 있습니다.

sum / N (sum overflow문제는 무시하더라도) 부터 0 까지 모두다 검사할 필요없이 중간지점을 검사해서 가능하면 그 위를/ 아니면 그 아래를 반복하면 됩니다.
이분법/bisection method 등을 찾아보세요, JMBook의 12장 최적화 문제 결정 문제로 바꿔 풀기 에도 잘 나와 있습니다 :)

zeikar 8년 전 0

이분법 비슷하게 해서 통과했습니다!

감사합니다.

알고리즘 참 어렵네요..ㅠㅠ

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

문제

문제

출처

ICPC

1654 랜선자르기 시간초과 질문

zeikar 8년 전 0

mastojun 8년 전 5

zeikar 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말