글 읽기 - 시간초과

sminhyuck 4년 전 0

정답을 찾기 위해 완전탐색을 하였습니다.

제출시 시간초과가 뜨는데, 가지치기를 더 어떻게 해줘야 시간을 줄일 수 있을지 잘 모르겠습니다.

조언 부탁드립니다!

#include <iostream>
using namespace std;

int N, M, L;
int Q[1000], S[1000];
int MAX; // 가장 큰 최솟값을 나타냄

void init() {
	cin >> N >> M >> L;
	for (int i = 0; i < M; i++)
		cin >> S[i];
	for (int i = 0; i < N; i++)
		cin >> Q[i];
}

int min(int a, int b) {
	if (a >= b) return b;
	else return a;
}

// 모든 경우를 다 탐색해야함
// 자른 케익 조각의 길이, 자른 횟수, 다음부터 탐색할 위치, 잘라야할 횟수
void DFS(int length, int slice, int next, int index, int MIN) {
	if (slice == index) {
		if (MIN > MAX) MAX = MIN;
		return;
	}

	if (MAX >= MIN) return;

	for (int i = next-1 ; i >= index-slice-1; i--) {
		int left = length - S[i];
		int small = min(left, S[i]);

		if (MIN > small) DFS(S[i], slice + 1, i, index, small);
		else DFS(S[i], slice + 1, i, index, MIN);
	}
}

int main() {
	init();
	for (int i = 0; i < N; i++) {
		MAX = 0;
		DFS(L, 0, M, Q[i], L);
		cout << MAX << endl;
	}
}

djm03178 4년 전 2

가지치기는 99.9%의 경우 올바른 해법이 아닙니다.

이분탐색을 생각해 보세요.

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

문제

문제

출처

ICPC

시간초과

sminhyuck 4년 전 0

djm03178 4년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말