글 읽기 - 동적계획법의 적용에 대해 질문이 있습니다..

furyhunter 7년 전 1

재귀로 아래와 같이 작성해서 이것저것 돌려보는데 정답은 나오는 것 같습니다.

근데 제출해본 결과 시간 초과가 뜨더라구요..

시간을 줄이기 위해 동적계획법을 어떻게 적용하면 될지 감이 안와서 조언을 구합니다..

각 단계에서의 최댓값을 단일 배열에 저장해서 이용하는건가요?

감이 잘 안오네요..

#include <iostream>

using namespace std;

//계단의 갯수 N
//1. 계단은 한번에 한개 또는 두개씩 오를 수 있음.
//2. 연속된 3개의 계단을 모두 밣아서는 안됨.
//3. 마지막 계단은 반드시 밣아야 함.

int max = 0;

int check(int *stair, int N, int n, int count, int score)
{
	int temp = 0;

	if (n > N)
		return score;

	if (count == 3)
		return score;

	score += stair[n];

	//n + 1 & count != 3 & n <= N
	temp = check(stair, N, n + 1, ++count, score);
	if (::max < temp)
		::max = temp;

	//n + 2 & n <= N
	temp = check(stair, N, n + 2, 1, score);
	if (::max < temp)
		::max = temp;

	return score;
}


int main()
{
	int N;
	int *stair;

	cin >> N;

	stair = new int[N + 1];

	stair[0] = 0;

	for (int i = 1; i <= N; i++)
		cin >> stair[i];

	check(stair, N, 1, 1, ::max);

	cout << ::max << "\n";

	delete stair;
}

waylight3 7년 전 19

가능한 경우의 수를 어떤 공간에 펼쳐놓는다고 생각해봅시다. 이 문제의 경우, i번째 계단에 대한 상태는 이전 계단에서 1칸 올라왔는지 2칸 올라왔는지만 알면 결정됩니다. 왜냐하면 그 이전의 정보는 몇 칸 올라왔는지를 제외하면 답을 구하는 데 전혀 필요가 없기 때문입니다. 따라서 (계단 수) X 2 만큼의 공간만큼 일종의 해 공간?이 존재합니다. 그렇다면, 이는 300 X 2의 2차원 dp테이블이 되니 이것만 채우면 답은 테이블 마지막에 들어있겠군요!

그럼 테이블을 어떻게 채우냐가 문제인데, 이 문제에서 계단은 올라갈수만 있다고 했으므로 다음과 같이 경우를 나눠볼 수 있습니다.

1. 방금 1계단 올라온 경우, 다시 1계단을 오르면 연속된 3계단을 밟게 됩니다. 따라서 이 경우 무조건 2계단을 뛰어야 합니다.

2. 방금 2계단 올라온 경우, 1계단 올라도 되고 2계단 올라도 됩니다.

따라서 다음과 같이 dp를 채워나갈 수 있습니다. 그렇다면 답은 dp[마지막 계단][1]과 dp[마지막 계단[2] 중 큰 값이겠군요!

(코드에서 step[i]는 i번째 계단의 점수를 의미합니다.)

    dp[1][1] = dp[1][2] = step[1];
    for (int i = 2; i <= n; i++) {
        dp[i][1] = dp[i-1][2] + step[i];
        dp[i][2] = max(dp[i-2][1], dp[i-2][2]) + step[i];
    }

furyhunter 7년 전 0

결국 중요한건 다음 인덱스의 계산을 위해서 필요한 이전단계들이 무엇인지 파악하는게 중요한거군요!

자세한 설명 감사합니다!

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