글 읽기 - DP 고수 님들!!!2579 계단 오르기

seanrocket17 7년 전 0

2차원으로 dp를 세우고 dp[i][j]에서 i가 몇 번째 계단 인지 일것 같기는 한데 j를 무엇으로 정의해야 하는지를 모르겠습니다.

도와주세요..

kesakiyo 7년 전 0

i번째 계단을 밟고 있을 때 몇번째 계단을 밟을지 결정하는데에는 어떤 값을 알고있어야 하는지

생각해 본다면 j는 쉽게 결정할 수 있습니다.

seanrocket17 7년 전 0

그럼 Dp[i][j]를 i번째 계단을 밝고 있을때 j계단을 올라갈때 최댓값으로 정의하면 되나요??

근데 연속해서 세 계단을 밟으면 안된다는 것은 어떻게 처리를 하죠???

kesakiyo 7년 전 0

i번째 계단을 밟고 있는데 이 계단은 이전으로부터 j번 연속한 계단이다. 이 때의 최대 점수

라고 하면 걱정하고 있는 모든것이 해결되지 않을까요?

seanrocket17 7년 전 0

아 그럼 계단을 한칸 올라가면 j+1 하고 두칸 올라가면 0으로 초기화 시키면 되겠네요. 우선 코드를 짜보고 안되면 올리겠습니다. 감사합니다 kesakiyo

seanrocket17 7년 전 0

아래는 틀린 코드인데 어디가 틀렸는지 좀 찾아주세요

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <math.h>
using namespace std;

int main()
{
    int n, arr[310], D[310][4];
    int ans = -1;
    scanf("%d",&n);
    for (int i = 0; i < n; i++)
        scanf("%d",&arr[i]);
    for (int i = 0; i < 310; i++)
        for (int j = 0; j < 4; j++)
            D[i][j] = -1;
    D[0][0] = D[0][1] = D[0][2] = D[0][3] = 0;
    for (int i = 0; i < n; i++){
        for (int j = 0; j < 3; j++){
            if (j != 2){
                D[i + 1][j + 1] = max(D[i][j] + arr[i + 1], D[i + 1][j + 1]);
                D[i + 2][0] = max(D[i][j] + arr[i + 2], D[i + 2][0]);
            }
            else D[i + 2][0] = max(D[i][j] + arr[i + 2], D[i + 2][0]);
        }
    }
    for (int i = 0; i < 4; i++)
        ans = max(ans, D[n + 1][i]);
    printf("%d",ans);
}

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

문제

문제

출처

ICPC

DP 고수 님들!!!2579 계단 오르기

seanrocket17 7년 전 0

kesakiyo 7년 전 0

seanrocket17 7년 전 0

kesakiyo 7년 전 0

seanrocket17 7년 전 0

seanrocket17 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말