[2156] 포도주 시식

문제 링크

 

배열에서 아래와 같은 규칙에 따라 수를 선택했을 때 최대값을 찾는 문제이다.

1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.

2번 조건에서의 연속으로 3잔을 모두 마실 수 없다는 것이 중요하다.

예시 입력은 6, 10, 13, 9, 8, 1이 주어졌다. 이를 배열로 표현하면 아래와 같다.

개발 편의상 배열의 크기를 N+1로 설정했다.

dp 배열을 만들어서 i번째 까지 선택한 값의 최대값을 저장한다.dp 배열의 i번째 원소를 업데이트하는 경우의 수는 다음과 같다.

• i-1과 i를 선택했을 경우
• i와 i-2를 선택했을 경우
• i를 선택하지 않을 경우

이 세 조건을 통해 연속으로 3개의 수를 선택하지 않도록 한다.

주어진 예시의 3번째 배열을 업데이트하는 예시를 살펴본다.

 

1. i-1과 i를 선택했을 경우

• 연속으로 두 개를 선택했기 때문에 i-3까지의 합을 더해야한다. dp[0]과 arr[2], arr[3]을 선택하여 23을 얻을 수 있다.

 

2. i와 i-2를 선택했을 경우

• 1개를 건너 띄우고 선택했다. dp[1]과 arr[3]을 선택하여 19를 얻을 수 있다.

 

3. i를 선택하지 않을 경우

• 3번째를 선택하이 않고 이전의 합을 가져온다. dp[2]를 선택하여 16을 얻을 수 있다.

이렇게 구한 세 가지 중 가장 큰 합은 i-1과 i를 선택했을 경우인 23이다. 이 값을 dp[3]에 저장한다.

 

위를 코드로 표현하면 아래와 같다.

x
for (int i = 3; i <= N; i++)
{
    dp[i] = max({ A[i] + dp[i - 2], A[i] + A[i - 1] + dp[i - 3], dp[i - 1] });
}