글 읽기 - [C++17] cache라는 특별한 배열이 있는건가요?

choah76 1년 전 0

시간초과가 나던 코드에 어떤 분이 알고리즘은 비슷한데 cache배열을 추가한 코드가 있길래 적용해보았습니다.

9줄에 cache배열을 선언하고 17, 18, 41줄을 추가했습니다.

그랬더니 시간초과가 나지 않더군요

그런데 cache배열은 memset으로 -1값을 넣는것 말고는 어떤 곳에서도 cache배열값을 건드리는 부분이 없는데 왜 17, 18번째 줄이 동작하여 시간이

감소되는지가 궁금합니다

#include <iostream>
#include <memory.h>
using namespace std;

#define INF 987654321
#define MAXK 500
#define endl '\n'

int cache[MAXK + 1][MAXK + 1];
int files[MAXK];
int pSum[MAXK];	// pSum[i] = 0번째 파일부터 i번째 파일까지의 누적 합

int dp(int l, int r) {
	if (l == r)
		return files[l];

	int& ret = cache[l][r];
	if (ret != -1)	return ret;

	ret = INF;

	int p1 = pSum[r];
	int p2 = l > 0 ? pSum[l - 1] : 0;
	int sum = p1 - p2;

	for (int i = l; i < r; i++)
		ret = min(ret, dp(l, i) + dp(i + 1, r) + sum);

	return ret;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int T;
	cin >> T;

	while (T--) {
		memset(cache, -1, sizeof(cache));
		int K;
		cin >> K;

		for (int i = 0; i < K; i++) {
			cin >> files[i];
			pSum[i] = files[i];

			if (i > 0)
				pSum[i] += pSum[i - 1];
		}

		int ans = INF;
		for (int i = 0; i < K; i++)
			ans = min(ans, dp(0, i) + dp(i + 1, K - 1));

		cout << ans << endl;
	}

	return 0;
}

adung7 1년 전 1

17번째줄에서 &(레퍼런스)는 내부 동작이 포인터와 동일합니다.

따라서 ret의 값을 바꾸는 행위는 ret이 가리키고 있는 곳의 값을 바꾸는 행위와 동일하게 되어

cache[l][r]의 값을 27번줄을 통해서 넣어주게 됩니다.

choah76 1년 전 0

아 그러면 cache배열이 메모이제이션을 담당하는 것이군요

감사합니다!!

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

문제

문제

출처

ICPC

[C++17] cache라는 특별한 배열이 있는건가요?

choah76 1년 전 0

adung7 1년 전 1

choah76 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말