글 읽기 - 반례까지 다 뚫었지만 안돼서 질문합니다 ㅠㅠ

snujoon 5년 전 0

진행은 계단오르기

https://www.acmicpc.net/proble...

처럼 하였구요

그런데 이 문제는 굳이 마셔야할 제약이 없어서 앞의 dp보다 새로운 dp가 작다면 그냥 앞의 dp를 계속 push_back했습니다.

이렇게 그냥 앞의 dp를 push_back한게 문제인가요?

#include <iostream>
#include <deque>
using namespace std;
int main()
{
    int n;
    cin >> n;
    //입력
    deque<int> s;
    for(int i=0;i<n;i++)
    {
        int inner;
        cin >> inner;
        s.push_back(inner);
    }
    //dp
    deque<int> dp;
    dp.push_back(s[0]);
    dp.push_back(s[1]);
    dp.push_back(max(s[0]+s[1],s[1]+s[2]));
    dp[1] = dp[0] + s[1];
    for(int i=3;i<n;i++)
    {
        if(dp[i-1]<max(dp[i-2]+s[i],s[i-1]+s[i]+dp[i-3]))
            dp.push_back(max(dp[i-2]+s[i],s[i-1]+s[i]+dp[i-3]));
        else
            dp.push_back(dp[i-1]);
    }
    cout << dp[n-1];
}

gaelim 5년 전 2

10 3 10

ac : 20

output : 13

10 3 10 3 11

ac : 31

output : 27

dp[i] => i 까지의 규칙을 준수하며 더한 합의 최댓값 으로 정의하시면 됩니다.

dp[2] 를 정의하실 때, 한 경우가 빠져 있으십니다.

snujoon 5년 전 0

감사합니다 ㅠㅠ dp[2] 정의가 생각보다 까다로웠습니다 ㅠㅠ 경우의 수를 다 생각하지 못했내요 어쨋든 도와주셔서 감사합니다 ㅎ

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

문제

문제

출처

ICPC

반례까지 다 뚫었지만 안돼서 질문합니다 ㅠㅠ

snujoon 5년 전 0

gaelim 5년 전 2

snujoon 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말