백준 2156번 : 포도주 시식 (C 언어)

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

2156번: 포도주 시식

Code:

#include <stdio.h>
#define max(a,b) ((a) > (b) ? (a) : (b))
 
int main() {
    int n;
    scanf("%d", &n);
    int arr[10001] = { 0, };
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &arr[i]);
    }
    int dp[10001] = { 0, };
    dp[1] = arr[1];
    dp[2] = arr[1] + arr[2];
    for (int i = 3; i <= n; i++)
    {
        dp[i]=max(dp[i - 2] + arr[i], max(dp[i - 1], dp[i - 3] + arr[i] + arr[i - 1]));
    }
    printf("%d", dp[n]);
    return 0;
}

문제풀이:

1. 문제 설명

이 문제는 수열에서 연속으로 세 개의 원소를 선택할 수 없는 조건 하에서, 선택할 수 있는 원소들의 최대합을 구하는 문제입니다. 수열의 길이는 사용자로부터 입력받는 정수 N에 의해 결정되며, 수열의 각 원소는 사용자로부터 입력받습니다.

2. 알고리즘

이 문제를 해결하기 위해 동적 계획법(DP)을 사용합니다. 동적 계획법은 복잡한 문제를 여러 개의 하위 문제로 분할하고, 그 하위 문제들의 해결책을 이용하여 원래 문제를 해결하는 방법입니다.

3. 코드 설명

1. 먼저, 수열의 길이 N을 입력 받습니다.
2. 그 후 N개의 수열 원소를 arr 배열에 저장합니다.
3. dp 배열을 초기화합니다. dp 배열은 dp[i]가 i번째까지의 원소를 선택했을 때 가능한 최대합을 가지도록 합니다. dp[1]은 첫 번째 원소, dp[2]는 첫 두 원소의 합으로 초기화합니다.
4. for문을 이용하여 세 번째 원소부터 N번째 원소까지 다음을 반복합니다:
   • dp[i]를 계산하기 위해, dp[i - 2] + arr[i] (즉, i번째 원소와 i - 2번째 원소까지의 최대합), dp[i - 1] (즉, i번째 원소를 선택하지 않고 i - 1번째 원소까지의 최대합), dp[i - 3] + arr[i] + arr[i - 1] (즉, i번째 원소와 i - 1번째 원소, 그리고 i - 3번째 원소까지의 최대합) 중 가장 큰 값을 선택합니다.
5. 마지막으로 dp[n]을 출력합니다. 이 값이 주어진 조건을 만족하면서 선택할 수 있는 원소들의 최대합이 됩니다.