josung50   4년 전

2차원 dp로 풀었습니다.

점화식으로는

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


제발 도와주세요.



djm03178   4년 전

코드를 제대로 분석해보지는 않았지만, 첫 번째 계단을 무조건 밟는 것으로 계산하는 듯 보이네요.
반례)
3
1
2
3
답은 5가 나와야 하지만, 4를 출력합니다.

xxsaintxx   4년 전

저 같은 경우에

반례)

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] ;

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