글 읽기 - 특이한 경우) 반례 원합니다.

travis97 2년 전 0

cout<<dp[n];하면 맞는 건 알고 있습니다.

그런데 어차피 dp에서 최대값이 dp[n]과 같은 값 아닌가요?

최대값은 안돼고 dp[n]은 되는 이유인 반례 찾아주신다면 정말로 감사하겠습니다 고수님덜

//백준 2579
#include<iostream>
#include<algorithm>
using namespace std;

int a[301];
int dp[301];
int n;

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) {cin>>a[i]; }
    dp[1]=a[1];
    dp[2]= a[1]+a[2];
    dp[3]= max(a[1],a[2])+a[3];
    for(int y=4;y<=n;y++){
        dp[y]= max(dp[y-2]+a[y], dp[y-3]+a[y-1]+a[y]);
    }
    cout<<*max_element(dp+1,dp+n+1);
}

hch6111 2년 전 1

마지막 블록을 꼭 밟으라고 되어 있어 그런 걸로 보입니다.

djm03178 2년 전 2

마지막 계단을 밟지 않는 케이스가 더 큰 값이 될 수도 있습니다.

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

문제

문제

출처

ICPC

특이한 경우) 반례 원합니다.

travis97 2년 전 0

hch6111 2년 전 1

djm03178 2년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말