글 읽기 - 11066번 knuth optimization 질문

lordly 5년 전 0

knuth's optimization을 이용해서 문제를 풀며 점화식을 이용한 풀이에서

c[i][j]란 dp[i][j]가 최소가 되게 하는 k(i < k < j)값을 저장하는 배열이라 정의할 때,

c[i][j-1] <= c[i][j] <= c[i+1][j]이 성립하고 이를 코드로

for (int i = 1; i <= n; ++i) { c[i-1][i] = i; }

와 같이 나타내는 것을 알았는데 잘 이해가 되질 않습니다.

왜 위의 점화식을 기준으로 c[i-1][i] 에 i를 대입하는 것인가요?

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <limits.h>
//BOJ 11066 FILE

int dp[501][501] = {};
int arr[501] = {};
int c[501][501] = {};

int file() {
	int n, num;
	scanf("%d", &n);
	
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &num);
		arr[i] = arr[i - 1] + num;
	}

	for (int i = 1; i <= n; ++i) {
		c[i-1][i] = i;
	}

	for (int diagonal = 2; diagonal <= n; diagonal++)
	{
		for (int i = 0; i <= n - diagonal; i++)
		{
			int j = i + diagonal;
			dp[i][j] = INT_MAX;
			for (int k = c[i][j - 1]; k <= c[i + 1][j]; k++) {
				int min = dp[i][k] + dp[k][j] + arr[j] - arr[i];
				if (dp[i][j] > min) {
					dp[i][j] = min;
					c[i][j] = k;
				}
			}
		}
	}
	return dp[0][n];
}

int main(void) {
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) {
		printf("%d\n", file());
	}
}

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

문제

문제

출처

ICPC

11066번 knuth optimization 질문

lordly 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말