글 읽기 - 동적계획법을 적용해봤는데 아무래도 뭔가 부족한것같아 조언을 구하고 싶습니다!

furyhunter 7년 전 0

dp라는 배열에 각 줄의 양쪽 max값과 그때의 삼각형에서의 index를 저장해서

다음 단계의 값을 구할 때 이용하도록 재귀 없이 코드를 짜봤습니다.

이렇게 된 경우 예제는 잘 풀리길래 제출해봤는데 오답이 나오더라구요

좀더 생각해보니까

3 3

3 0 3

3 0 0 3

3 0 50 0 3

같은 식으로 입력이 들어올 경우 제대로 결과가 안나오더라구요 ㅎㅎ

혹시 이런 경우까지 다 잡을 수 있도록 동적계획법을 적용하려면 어떻게 해야할지 조언해주시면 감사하겠습니다!

#include <iostream>

using namespace std;

//크기가 n인 숫자 삼각형이 들어옴.
//맨 위부터 시작해서 자신의 왼쪽 아래나 오른쪽 아래 수를 취하며 내려옴.
//마지막까지 내려왔을 때 최대값을 출력

//다음 단계 연산을 위해 필요한 정보는?
//현재 단계에서 사용한 인덱스가 몇인지
//현재 인덱스 n을 사용할 때 다음에는 n과 n+1만 사용될 수 있음.

//7
//10 15
//18 11 16 15
//20 25 18 15 23 20 19 19

//2개를 저장해볼까?
//7
//10 15
//18 16
//25 23
//...

int tri[501][501] = { 0 };		//삼각형 배열

int max_i(int n, int A, int B)	//인덱스를 받아 삼각형에서의 해당 값의 대소를 비교
{
	if (tri[n][A] > tri[n][B])
		return A;
	else
		return B;
}

int main()
{
	int N;
	int dp[501][4] = { 0 };		//0 : 왼쪽 값, 1 : 오른쪽 값, 2 : 왼쪽 인덱스, 3 : 오른쪽 인덱스

	cin >> N;
	
	for (int i = 0; i < N; i++)		//삼각형 채우기
	{
		for (int j = 0; j < i + 1; j++)
			cin >> tri[i][j];
	}

	dp[0][0] = dp[0][1] = tri[0][0];
	dp[1][0] = dp[0][0] + tri[1][0];
	dp[1][1] = dp[0][1] + tri[1][1];
	dp[1][2] = 0;
	dp[1][3] = 1;
	
	cout << 0 << " : " << dp[0][0] << " " << dp[0][1] << " " << dp[0][2] << " " << dp[0][3] << "\n";
	cout << 1 << " : " << dp[1][0] << " " << dp[1][1] << " " << dp[1][2] << " " << dp[1][3] << "\n";

	for (int i = 2; i < N; i++)
	{
		//이전 단계의 인덱스를 이용해 현재 단계의 인덱스 두개(n, n + 1)중 큰 값을 저장
		dp[i][2] = max_i(i, dp[i - 1][2], dp[i - 1][2] + 1);
		dp[i][3] = max_i(i, dp[i - 1][3], dp[i - 1][3] + 1);

		//앞에서 구한 인덱스를 이용해 현재 단계의 최대값을 저장
		dp[i][0] = dp[i - 1][0] + tri[i][dp[i][2]];
		dp[i][1] = dp[i - 1][1] + tri[i][dp[i][3]];

		cout << i << " : " << dp[i][0] << " " << dp[i][1] << " " << dp[i][2] << " " << dp[i][3] << "\n";
	}

	int A = dp[N - 1][0];
	int B = dp[N - 1][1];

	//마지막 단계에서 최대값을 출력
	if (A > B)
		cout << A << "\n";
	else
		cout << B << "\n";

	return 0;
}

onjo0127 7년 전 1

삼각형의 맨 위 꼭짓점을 (1,1)이라고 했을 때

dp[i][j] = (1,1)에서 (i,j)까지 내려오는 데 얻을 수 있는 수의 합의 최대값

이라고 정의하고 풀어보세요 ㅎㅎ

배열
int dp[2][555]
를 이용합니다.
여기서 dp[0][]은 이전 층까지의 합이 저장된 곳, dp[1][]은 이번 층의 합을 저장할 곳입니다.
그렇다면 x 층의 i번째 에서의 합은
dp[1][i ] = max(dp[0][i-1], dp[0][i]) + tri[x][i] 가 된다는 것을 알 수 있죠 (물론 i가 시작이나, 끝일 땐 따로 처리를 해줘야합니다)
dp[1][]을 모두 구하고 나면 dp[0][]으로 dp[1][]의 값들을 복사해준 뒤, 다음 x+1번 째 층을 계산하면 될 것 같습니다.
문제의 예제 input을 생각해보면
---------------------------------------------
x = 0 일 때
dp[1][0] = 7

//갱신 끝

dp[0][0] = dp[1][0]
---------------------------------------------
x = 1 일 때
dp[1][0] = 7+3
dp[1][1] = 7+8

//갱신 끝

dp[0][i] = dp[1][i]
-------------------------------------------
......
-------------------------------------------
x = k 일 때
dp[1][0] = dp[0][0] + tri[k][0]
dp[1][k] = dp[0][k-1] + tri[k][k]
else
dp[1][i] = max(dp[0][i-1], dp[0][i]) + tri[k][i]

//갱신 끝

dp[0][i] = dp[1][i]
----------------------------------------------
...
이런식으로 가겠죠

furyhunter 7년 전 0

조언 덕분에 잘 해결했습니다!

어떤 정보를 저장해야할지 처음 생각해내는게 참 어렵네요

감사합니다!

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

문제

문제

출처

ICPC

동적계획법을 적용해봤는데 아무래도 뭔가 부족한것같아 조언을 구하고 싶습니다!

furyhunter 7년 전 0

onjo0127 7년 전 1

ldg1291 7년 전 1

furyhunter 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말