글 읽기 - 요거 knuth optimization으로 못푸나요?,..

bubblepop 5년 전 1

s제출하니까 시간초과가 뜨는데 인풋범위가 5천까지 들어와서 그런건가요.. 다른 최적화 기법이 필요한건지 궁금합니다.

#include <stdio.h>
#define FOR(a,b) for(int a=0; a<(b); a++)
#define SIZE 5001
int opt[SIZE][SIZE];
int a[SIZE][SIZE];
int sum[SIZE][SIZE];
int cost[SIZE];
void init()
{
	FOR(i, SIZE){
		cost[i] = 0;
		a[i][i] = i;
		FOR(j, SIZE){
			opt[i][j] = sum[i][j] = 0;
		} 
	}
}
int main(void)
{
	//freopen("input.txt", "r", stdin);
	int TC;
	scanf("%d", &TC);
	FOR(tc, TC)
	{
		init();	
		int n;
		scanf("%d", &n);
		FOR(i, n){
			scanf("%d", &cost[i + 1]);
		}
		for (int i = 1; i <= n; i++){
			for (int j = i; j <= n; j++)
			{
				sum[i][j] = sum[i][j - 1] + cost[j];
			}
		}
		for (int len = 1; len <= n; len++){
			for (int i = 1; i + len <= n; i++){
				int j = i + len;
				opt[i][j] = 1e9;
				for (int k = a[i][j - 1]; k <= a[i + 1][j]; k++){
					if (opt[i][j] > opt[i][k] + opt[k + 1][j] + sum[i][j]){
						opt[i][j] = opt[i][k] + opt[k + 1][j] + sum[i][j];
						a[i][j] = k;
					}
				}
			}
		}
		printf("#%d %d\n", tc + 1, opt[1][n]);
	}
	return 0;
}

jh05013 5년 전 1

Knuth Optimization 문제가 맞습니다. 입력이 굉장히 많이 들어와서 그런지 잘 짜도 1.5초 이상도 갈 수 있는 것으로 보입니다.

이것이 원인인지는 모르겠으나 sum을 O(N^2) 전처리 후 O(1)으로 사용하셨는데, O(N) 전처리 후 O(1)으로 사용하는 것이 가능합니다.

koosaga 5년 전 1

init 함수가 비효율적입니다. N = 1짜리 테스트 케이스가 1000개 들어오면 시간 초과가 무조건 나요. N^2에 비례하는 시간에 초기화하셔아 합니다. 지금은 5000^2에 비례하는 시간이 듭니다.

bubblepop 5년 전 0

헐.. 정말 고맙습니다. 생각지도 못한곳에서 연산이 너무 많이 이루어지고 있었군요!

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

문제

문제

출처

ICPC

요거 knuth optimization으로 못푸나요?,..

bubblepop 5년 전 1

jh05013 5년 전 1

koosaga 5년 전 1

bubblepop 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말