백준 23029번 시식 코너는 나의 것

🔒[문제 url]

https://www.acmicpc.net/problem/23029

🪄전체 코드

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

int n;
int food[100001];
int dp[100001][3];

void INPUT()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> food[i];
}


void SOLVE()
{
    /*
    dp[i][0] : i번 코너 음식을 먹지 않는 경우
    dp[i][1] : i번 코너 음식을 절반만 먹는 경우
    dp[i][2] : i번 코너 음식을 모두 먹는 경우
    
    2이상인 i에 대해, 경우의 수는 다음과 같다.
    1) i-1번 코너 음식을 먹지 않은 경우 : i번 음식을 먹지 않거나, 모두 먹을 수 있다.
    2) i-1번 코너 음식을 절반만 먹은 경우 : i번 음식을 먹을 수 없다.
    3) i-1번 코너 음식을 모두 먹은 경우 : i번 음식을 먹지 않거나, 절반만 먹을 수 있다.
    
    즉,
    1) i번 음식을 먹지 않을 경우 : max(dp[i-1][0],max(dp[i-1][1],dp[i-1][2]))
    2) i번 음식을 절반만 먹는 경우 : dp[i][1] = dp[i-1][2] + food[i] / 2
    3) i번 음식을 모두 먹는 경우 : dp[i-1][0] + food[i]
    */
    
    dp[1][1] = food[1];
    dp[1][2] = food[1];

    dp[2][0] = food[1];
    dp[2][1] = food[1] + food[2] / 2;
    dp[2][2] = food[2];

    int ans = max(dp[2][1],dp[2][2]);
    for(int i = 3; i <= n; i++)
    {
        dp[i][0] = max(dp[i-1][0],max(dp[i-1][1],dp[i-1][2]));
        dp[i][1] = dp[i-1][2] + food[i] / 2;
        dp[i][2] = dp[i-1][0] + food[i];

        ans = max(dp[i][0],max(dp[i][1],dp[i][2]));
    }

    cout << ans;
}

int main()
{
    INPUT();
    SOLVE();
}

🥇문제 후기

GOLD5 미만 난이도는 알고리즘 및 풀이 설명을 주석으로 대체합니다.
주석을 참고해주세요.