글 읽기 - 제 풀이가 DP의 Top-Down 방식이 맞나요?

vlvkrhksgml0902 1년 전 1

다 풀고 나서야 남들은 2차원 배열로 푸는걸 알긴 했습니다..

제가 쓴 알고리즘이 Top_Down이 맞는지, 혹은 개선할 것이 있는지 알려주시면 감사하겠습니다.

#include <iostream>
#include <algorithm>

int func(int n, int* arr, int* memo);

int main() {
	std::cin.tie(NULL);
	std::cout.tie(NULL);
	std::ios::sync_with_stdio(false);

	int n, i;
	std::cin >> n;
	int* arr = new int[n + 1] {0, };
	for (i = 1; i <= n; i++) { // 계단 저장
		std::cin >> arr[i];
	}

	int* memo = new int[n + 1] {0, }; // 메모할 배열
	std::cout << func(n, arr, memo);
}

int func(int n, int* arr, int* memo) {
	if (n == 0) {
		return arr[0];
	}
	else if (n == 1) {
		if (memo[1] == 0) {
			memo[1] = arr[1];
		}
		return memo[1];
	}
	else if (n == 2) {
		if (memo[2] == 0) {
			memo[2] = arr[n] + arr[n - 1];
		}
		return memo[2];
	}
	else {
		if (memo[n] == 0) { // 이미 푼 n이면 메모에서 가져다 쓰기, 아니면 메모에 넣고 쓰기
			int a = func(n - 2, arr, memo);
			int b = func(n - 3, arr, memo) + arr[n - 1];
			memo[n] = std::max(a, b) + arr[n];
		}
		return memo[n];
	}
}

dldyddlwl 1년 전 0

// 네, 맞습니다. 그리고 다음 질문에 대해서는 틀린게 없으니 딱히 개선이라고 하기도 그렇군요!! 다만
// 조금 더 코드를 줄여볼 수는 있겠습니다~
int func(int n, int* arr, int* memo) {
	if (n < 0)        
        return 0;        // 음수가 되는 경우 (n==1,n==2인 경우에도 func가 0을 리턴하므로 기존의 조건문과 같게됨!!)
	
		if (memo[n] == 0) { 
			int a = func(n - 2, arr, memo);
			int b = func(n - 3, arr, memo) + arr[n - 1];
			memo[n] = std::max(a, b) + arr[n];
		}
		return memo[n];
}

vlvkrhksgml0902 1년 전 0

감사합니다!

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

문제

문제

출처

ICPC

제 풀이가 DP의 Top-Down 방식이 맞나요?

vlvkrhksgml0902 1년 전 1

dldyddlwl 1년 전 0

vlvkrhksgml0902 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말