연속 선택 없이 혜택 최대화

상태의 뜻을 먼저 한 문장으로 정해요

vector·반복·조건·함수를 알고 시작해요. 이번에는 작은 문제의 답을 저장하고, 다음 계산에 이어 써요. <algorithm>의 max(a,b)는 두 값 중 큰 것을 반환해요.

선택할 때 바로 이웃한 항목을 함께 고르지 않는다고 해요. dp[i]를 ‘앞 i개 항목에서 얻을 수 있는 최대 합’으로 정해요. 인덱스 i는 마지막 항목의 번호가 아니라 고려한 항목 수예요. dp[0]은 아무것도 고르지 않은 합 0이에요. vector<int> dp(n + 1, 0);은 0으로 초기화한 칸 n+1개를 만들어요. 항목 수 0부터 n까지를 저장하므로 n개가 아니라 n+1개가 필요해요.

마지막 항목을 고르는 경우와 안 고르는 경우를 나눠요

앞 i개에서 마지막 값 values[i-1]을 안 고르면 앞 i−1개의 최댓값을 그대로 쓸 수 있어요. 마지막을 고르면 바로 이전 항목은 못 골라요. 그래서 앞 i−2개에서 얻은 최댓값에 마지막 값을 더해요.

dp[i] = max(dp[i - 1], dp[i - 2] + values[i - 1]);

이 식은 i≥2일 때 써요. 하나만 있을 때는 그 값이 0 이상이므로 고르는 것이 최선이고 dp[1]=values[0]이에요. 아무것도 없는 경우에는 dp[1]을 만들거나 첫 값을 읽지 않아요.

작은 표에서 두 후보를 직접 비교해요

예제 {4,1,6}을 따라가 봐요.

앞 세 개를 다 본 뒤 최대 합은 10이에요. 값 5가 맨 뒤에 더 있다면 다음 두 후보는 얼마일까요? 안 고르면 dp[3]=10, 고르면 dp[2]+5=9예요. 따라서 다음 답은 10이에요. 매번 큰 항목부터 고르는 방식과 달리, 각 끝 위치에서 두 경우를 빠짐없이 비교해요.

직접 풀어봐요

values는 항목별 혜택이고, 항목을 하나 선택할 때마다 fee만큼 비용이 들어요. 바로 이웃한 두 인덱스는 함께 선택할 수 없어요. 선택한 항목들의 혜택 합에서 선택한 개수×fee를 뺀 순혜택의 최댓값을 반환해요. 아무것도 고르지 않아도 되고 그 순혜택은 0이에요.

설명 예제는 비용 없이 합을 구했지만, 이번 과제에는 선택마다 비용이 있어요. 마지막 항목을 선택하는 후보가 얼마인지, 하나만 있을 때 선택하지 않는 편이 나을 수도 있는지 계약에 맞춰 판단해요.

solution(vector<int> values, int fee)의 values 길이는 0100, 각 원소와 fee는 01000이에요. 실행용 입력은 첫 줄 길이 n, 다음 줄 n개 혜택, 마지막 줄 fee예요. n=0이면 혜택 줄은 비어 있어요. 출력은 반환값이에요. 하네스가 입력·출력을 처리해요.

예시 1: values={6,2,7,3}, fee=1 → 11. 6·7을 고르면 혜택 13에서 두 항목의 비용 2를 빼요. 예시 2: values={2,9,4}, fee=3 → 6. 가운데만 골라 혜택 9에서 비용 3을 빼요.

4
6 2 7 3
1

11

3
2 9 4
3

6