글 읽기 - 아래로 내려가면 왜 안될까요....?

juyeon25 2년 전 0

마지막 계단을 무조건 밟아야 하기 때문에, 처음시도는 위에서부터 내려가는 방식으로 구현했습니다.

점화식 "dp[n]는 n번째 계단을 '밟았을' 때의 최대값" 으로 정의했습니다.

일반적인 해답으로는 문제를 맞췄는데, 거꾸로 내려오면, 뭐가 문제일까요? 반례라도 부탁드립니다ㅠㅠ

#include <iostream>
#include <vector>
using namespace std;

int main(void) {
    int n;
    cin>>n;

    vector <int> v(n);
    vector <int> dp(n, 0);

    for(int i = 0; i < n; i ++){
        cin>> v[i];
    }

    dp[n-1] = v[n-1];
    dp[n-2] = v[n-1]+v[n-2];
    dp[n-3] = max(v[n-2],v[n-3])+v[n-1];

    for(int i = n-4; i >= 0; i--){
        //dp[k]: k번째 계단을 밟았을 때 가질 수 있는 가장 큰 수
        dp[i] = max(dp[i+3] + v[i+1] + v[i], dp[i+2] + v[i]);
    }
    //마지막 계단은 넘어뛸 수 있음
    dp[0] = max(dp[1], dp[0]);
    cout<<dp[0]<<endl;
    return 0;
}

profrog 2년 전 1

반례입니다!

6
6
6
1
1
6
6
코드의 값 ->24,실제 값 ->19

showtsa 2년 전 0

저랑 비슷하게 틀리셨네요

글쓴이분 코드 중에

dp[n-3] = max(v[n-2],v[n-3])+v[n-1]; 이 아니라

dp[n-3] = v[n-3]+v[n-1]; 이 되어야 하지 않을까요?

글쓴이님 코드는 첫 번쨰 칸 -> 두 번째와 세 번째 중 점수가 큰 곳으로 가는데

세 번째 칸으로 가는 방법은 첫 번째 칸 -> 세 번째 칸 밖에 없으니까요,,

많이 늦어서 이미 푸셨겠지만, 혹시나 도움될 분들이 계실까 답변 남깁니다.

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

문제

문제

출처

ICPC

아래로 내려가면 왜 안될까요....?

juyeon25 2년 전 0

profrog 2년 전 1

showtsa 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말