글 읽기 - dp로 풀었는데 어디가 틀린지 모르겠습니다 ㅠㅠ..

josung50 6년 전 0

2차원 dp로 풀었습니다.

점화식으로는

DP[i][j] = MAX( DP[i][j-2] , S[j-1] + DP[i][j-3]) + S[j] 로 세웠구요!

제발 도와주세요.

#include<iostream>
using namespace std;

int stairs[301];
int dp[301][301];

int n;

int compare_max(int i, int j);
void print();

int main() {
	cin >> n;
	stairs[0] = 0;
	for (int i = 1; i <= n; i++)
		cin >> stairs[i];

	/* dp 초기값 */
	dp[0][0] = 0;
	for (int i = 1; i <= n; i++)
		dp[i][i] = stairs[i];


	/* dp 채우기 */		
	for (int i = n; i >= 1; i--) {
		for (int j = i; j <= n; j++) {
			if ( (j - i == 2) || (j - i == 1))
				dp[i][j] = stairs[i] + stairs[j];
			else if (j-i >= 3){
				dp[i][j] = compare_max(i, j) + stairs[j];
			}
		}
	}


	cout << dp[1][n];
	//print();
}

int compare_max(int i, int j) {
	if (dp[i][j - 2] >= stairs[j - 1] + dp[i][j - 3])
		return dp[i][j - 2];
	else return (stairs[j - 1] + dp[i][j - 3]);
}

void print() {
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
			cout << dp[i][j] << " ";
		cout << "\n";
	}
}

djm03178 6년 전 0

코드를 제대로 분석해보지는 않았지만, 첫 번째 계단을 무조건 밟는 것으로 계산하는 듯 보이네요.

반례)

답은 5가 나와야 하지만, 4를 출력합니다.

xxsaintxx 6년 전 0

저 같은 경우에

반례)

6
1 1 0 0 1 1

출력이 3으로 나와야 되나

4가 나와 수정했었습니다.

ans[1][1] = arr[1]; // 초기값 셋팅( 첫계단일때는 경우의 수가 첫번째 일때밖에 존재하지 않는다 )

   // 해당 계단을 안 밟았을 때
    if(j == 0) ans[i][j] = Math.max( Math.max(ans[i-1][0], ans[i-1][1]), ans[i-1][2] );
    // 해당 계단이 첫 번째 일때
    //if(j == 1) ans[i][j] = ans[i-1][0] + arr[i] ;
    if(j == 1) ans[i][j] = Math.max(ans[i-2][1], ans[i-2][2]) + arr[i] ;
    // 해당 계단이 두 번째 일때
    if(j == 2) ans[i][j] = ans[i-1][1] + arr[i] ;

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

문제

문제

출처

ICPC

dp로 풀었는데 어디가 틀린지 모르겠습니다 ㅠㅠ..

josung50 6년 전 0

djm03178 6년 전 0

xxsaintxx 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말