글 읽기 - dp가 너무 어렵습니다.

dlxogh376 7년 전 0

코드를 이와 같이 재귀로 했는데요..

dp가 메모이제이션을 통한 재귀 호출 반복을 막는거라는 건 알겠습니다.

여기서 예를 들면 recursive의 반복을 막아주기 위해 캐시 배열을 선언해서 저장해 놓는거라고 알고있는데요.. 문제는 그걸 어떻게 여기서 변형해야 할지를 모르겠습니다. ㅠㅠ

설명좀 해주실분 안계신가요?

#pragma warning(disable:4996)
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <stack>
#include <queue>
 
using namespace std;
 
 
int stair[333];
int scoreBoard[11111];
int n;
int maxScore = 0;
 
void recursive(int curNum,int wha, int score) {
    if (curNum == n) {
        if (maxScore < score) maxScore = score;
        return;
    }
    else if (curNum > n) {
        return;
    }
    if (wha == 0) {
        recursive(curNum + 1, 1, score + stair[curNum + 1]);
        recursive(curNum + 2, 0, score + stair[curNum + 2]);
    }
    else if(wha == 1){
        recursive(curNum + 2, 0, score + stair[curNum + 2]);
    }
    else {
        recursive(curNum + 1, 0, score + stair[curNum + 1]);
        recursive(curNum + 2, 0, score + stair[curNum + 2]);
    }
}
 
 
int main() {
    scanf("%d",&n);
    for (int i = 1; i <= n; i++) {
        scanf("%d",&stair[i]);
    }
    recursive(0,2,0);  //현재 계단 번호, 연속인지 판단 ,현재 점수 
 
    printf("%d\n",maxScore);
    return 0;
}

zlzmsrhak 7년 전 1

메모이제이션은 함수가 호출될 때의 인자가 같은 경우 같은 값을 리턴하는 함수에 대해서,

계산한 값을 저장하여 같은 인자에 대해서는 두 번 이상 계산을 하지 않도록 하는 방법입니다.

이것을 위해서는 재귀함수를 그냥 바꿀 수는 없고, 함수 정의와 점화식을 신경써주어야 합니다.

먼저 함수의 정의를

int recursive(int curNum,int wha) : curNum번째 계단에서 시작하고, 연속 상태가 wha일 때 얻을 수 있는 최대 이득

으로 수정하는 것으로 시작하는 것으로 시작해야 합니다.

재귀 코드를 참고하면, (틀릴 수도 있습니다)

wha = 0인 경우 recursive(curNum + 1, 1) + stair[curNum + 1], recursive(curNum + 2, 0) + stair[curNum + 2]중 큰 값,

wha =1인 경우 recursive(curNum + 2, 0) + stair[curNum + 2]

wha = 2인 경우 recursive(curNum + 1, 0) + stair[curNum + 1],

recursive(curNum + 2, 0) + stair[curNum + 2] 중 큰 값으로 구할 수 있겠습니다.

메모이제이션 기본 틀인 캐시 배열도 추가해야 합니다.

dlxogh376 7년 전 0

감사합니다..
그래서 좀 고쳐봤는데 여기서 어떤 문제가 있는지 피드백좀 부탁드려도 될까요?

#pragma warning(disable:4996)
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <stack>
#include <queue>

using namespace std;


int stair[333];
int cache[333][3];
int n;

int max(int a, int b) {
	return a > b ? a : b;
}


int recursive(int curNum, int wha) {
	if (curNum == n) {
		return cache[curNum][wha];
	}
	else if (curNum > n) {
		return 0;
	}
	int& ret = cache[curNum][wha];
	if (ret != 0) return ret;
	if (wha == 0) {
		return ret = max(recursive(curNum + 1, 1) + stair[curNum + 1], recursive(curNum + 2, 0) + stair[curNum + 2]);
	}
	else if (wha == 1) {
		return ret = recursive(curNum + 2, 0)+stair[curNum + 2];
	}
	else {
		return ret = max(recursive(curNum + 1, 0) + stair[curNum + 1], recursive(curNum + 2, 0)+stair[curNum + 2]);
	}
}


int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &stair[i]);
	}

	for (int i = 0; i < 333; i++) {
		cache[i][0] = 0;
		cache[i][1] = 0;
		cache[i][2] = 0;
	}
	int ans= recursive(0, 2);  //현재 계단 번호, 연속인지 판단

	printf("%d\n", ans);
	return 0;
}

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

문제

문제

출처

ICPC

dp가 너무 어렵습니다.

dlxogh376 7년 전 0

zlzmsrhak 7년 전 1

dlxogh376 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말