글 읽기 - 어떤 부분에서 메모리의 차이가 나는건지 알고 싶습니다.

kangsy763 4년 전 0

주석안의 식을 이용했을 때에는 5016kb에 시간도 얼마 안걸리는데

바깥의 식을 이용했을 때에는 36144kb에 36ms가 걸립니다.

if (n % 3 == 0 && n % 2 == 0) memo[n] = min(dp(n / 3), min(dp(n / 2), dp(n - 1)))+1;

이 줄에 min 안에 min이 들어가면서 dp를 많이 불러오게 되어서가 그 이유일까요 ? ?

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define INF 987654321
int memo[1000001];

int dp(int n) {
	if (n == 1) return 0;
	if (memo[n] != (-1)) return memo[n];
	int ret = INF;
	/*if (n % 2 == 0) ret = 1 + dp(n / 2);
	if (n % 3 == 0) ret = min(ret, 1 + dp(n / 3));
	if (n % 6 != 0)
		ret = min(ret, 1 + dp(n - 1));

	return memo[n] = ret;*/

	if (n % 3 == 0 && n % 2 == 0) memo[n] = min(dp(n / 3), min(dp(n / 2), dp(n - 1)))+1;
	else if (n % 3==0) memo[n] = min(dp(n / 3), dp(n - 1))+1;
	else if (n % 2==0) memo[n] = min(dp(n / 2), dp(n - 1))+1;
	else memo[n] = dp(n - 1) + 1;
	return memo[n];
}

int main() {
	int num;
	scanf("%d", &num);
	memset(memo, -1, sizeof(memo));
	printf("%d", dp(num));
	return 0;
}

ho94949 4년 전 1

n이 6의 배수일 때 위의 식은 n/2, n/3 만 호출하지만, 아래의 식은 n/3, n/2, n-1 모두 호출 하네요.

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

문제

문제

출처

ICPC

어떤 부분에서 메모리의 차이가 나는건지 알고 싶습니다.

kangsy763 4년 전 0

ho94949 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말