글 읽기 - [흑흑] 풀이 슬라이드를 참고하여 풀었는데 여전히 시간이 초과됩니다.

joon11132 4년 전 0

안녕하세요,

ho94949님께서 올려주신 풀이 슬라이드의 N <= 500 에서의 동적 계획법에 따라서 푼다고 풀었는데 여전히 시간초과가 납니다 ㅠㅠ

N <= 500 에서 제시해주신 알고리즘은 '수학적인 성질을 더 관찰하지 않고는 시간복잡도를 줄이기 어려운' 알고리즘이라고는 하셨으나 제 코드가 문제인지 이 문제도 시간초과가 납니다.

조건 가지치기를 더 할 수 있는지, 아니면 제 코드가 아예 틀린것인지 알려주시면 감사하겠습니다 ㅠㅠ

#include<stdio.h>
int N, a[1500];
int mod(int n) {
	int ret = n % N;
	if (ret >= 0) return ret;
	else return ret + N;
}
int REC(int i, int j, int k) {
	if (i < 0 || j < 0 || k < 0 || i < j) return 0;	// invalid case
	if (j==0) {
		if (k == 0) return 1;	// 답을 찾음.
		else return 0;	// invalid
	}
	if (REC(i - 1, j - 1, mod(k - a[i]))) {	// true라면,
		printf("%d ", a[i]);
		return 1;
	}
	else if(REC(i - 1, j, k)) return 1;	// false라면,
	return 0;
}

int main() {
	scanf("%d", &N);
	for (int i = 1; i <= 2 * N - 1; i++) scanf("%d", a + i);
	if(!REC(2*N-1,N,0)) printf("-1");	// 2N-1 개의 수들 중에 N개를 더해서 N으로 나눴을 때 나머지가 0인게 있는지
	return 0;
}

Green55 4년 전 1

이건 동적계획법이 아닙니다.. dp를 좀 더 공부 해보신 다음에 푸시는게 좋을 것 같아요.

joon11132 4년 전 0

세상에 테이블이 필요하군요, 감사합니다.

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

문제

문제

출처

ICPC

[흑흑] 풀이 슬라이드를 참고하여 풀었는데 여전히 시간이 초과됩니다.

joon11132 4년 전 0

Green55 4년 전 1

joon11132 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말