Gidhub BE Developer

[BOJ] 포도주 시식

2018-03-22
goodGid

Problem

Problem URL : 포도주 시식


[1] Answer Code (18. 03. 22)


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

int arr[10001];
int dp[10001];

int main(){
    int n;
    cin >> n;
    
    for(int i=1; i<=n; i++)
        scanf("%d",arr+i);
    
    dp[1] = arr[1];
    dp[2] = arr[1] + arr[2];
    
    int ans = max(dp[1],dp[2]); // [2]
    for(int i=3; i<=n; i++){
        dp[i] = max( dp[i-2], arr[i-1] + dp[i-3] ) + arr[i];
        dp[i] = max( dp[i], dp[i-1] );   // [1]
        ans = max( ans, dp[i]);
    }
    
    cout << ans << endl;
    return 0;
}






Code Review

[1] Answer Code (18. 03. 22)

  • [1] 조건문이 왜 필요한가 이해가 안됐다.

반례를 찾았다.

100, 400, 2, 1, 4, 200 주어졌을 때, 경우를 보자.

위의 점화식만으로 결과는 701이 나온다.

하지만 답은 100, 400, 4, 200 => 704가 나온다.

그렇다. 포도주를 2번 연속 안 먹을 경우가 존재한다.

  • 연속 2번 안 먹을 경우를 생각하지 못하여서 계속해서 틀렸다.

  • 추가적으로 주의할 점은
    n=2일 때 int ans = 0;일 경우 틀리게 되므로 ans = max( dp[1], dp[2]) 가 필요하다.


Comments

Index