[백준][C/C++] 2156 포도주 시식

문제

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

2156번: 포도주 시식

---

요약

조건을 만족하게 포도주를 선택해서 총량의 최대값 구하기

 

조건1: 나눠 마시기 불가 

조건2: 연속 3잔 불가

 

---

풀이

단서

1. 최댓값을 구하는 문제

2. 포도주를 하나씩 늘려가면서, i번째 포도주를 선택O or 선택X 하는 경우로 생각 가능 -> 규칙 찾기 가능

 

일반적인 DP 문제로 짐작 가능

=> 규칙을 먼저 찾자

=> DP니까 dp 변수 설정, 초기값, 점화식 수립할 것 염두

 

 

예시

먼저 예시를 들어보자

 

<포도주 총 개수 N=1 일 때>

경우의 수는 다음과 같다

1. 1번째 포도주 선택O 

2. 1번째 포도주 선택X 

 

최대: 무조건 포도주 선택하는 경우(1번)가 최대값임

 

<포도주 총 개수 N=2 일 때>

- 경우의수

1. XX

2. XO

3. OX

4. OO

 

최대: 무조건 모든 포도주 선택(4번)하는 게 최대값

 

<포도주 총 개수 N=3일 때>

여기서부터 문제 조건에 걸리는 것들이 나온다.(3개 연속 선택 불가능함)

- 경우의 수

1. XXX

2. XXO

3. XOX

4. OXX

5. OOX

6. OXO

7. XOO

 

최대: 여기부턴 고정 X(5, 6, 7번 중 하나)

 

N=1, N=2까지만 초기값으로 설정하자.

 

 

이제 실제 예시를 들어보자

6,10,13,9,8,1이라는 포도주 들어 있는 걸 테이블로 나타내면,

 

6	10	13	9	8	1
1번째	...	i-3번째	i-2번째	i-1번째	i번째

 

<포도주의 총 개수가 N=6일때>

일단 배열 2개를 준비한다. arr배열에는 포도주 값을 담고, dp배열엔 각 요소까지 갔을 때 최대값이 담겨있다고 하자.

 

끝 부분만 보면

- i번째 선택 안할 경우

1. ???OOX

2. ???OXX

3. ???XOX

4. ???XXX 

 

끝부분이 선택 안될 때, '3개 연속이 되면 안 된다'는 문제 조건에 위반될 일이 없다. 즉, i-1번째까지의 최대값과 같다.

점화식을 세워보면,

 

dp[i] = dp[i-1]

 

- i번째 선택 할 경우

1.???XXO 

2.???XOO

3.???OXO

 

점화식으로 나타내자

 

1, 3번 -> i-2 번째까지의 최대값 + i번째 값  -> dp[i] = dp[i-2] + arr[i]

2번 -> i-3 번째까지의 최대값 + i-1번째의 값 + i번째의 값 -> dp[i] = dp[i-3] + arr[i-1] + arr[i]

 

결국 dp[i] 는

1. dp[i-1]

2. dp[i-2] +arr[i]

3. dp[i-3] +arr[i-1] +arr[i]

1, 2, 3 중에 최대값이 될 것이다.

 

결론

1. 변수: arr배열, dp배열

2. 초기식

dp[1] = arr[1]
dp[2] = arr[1]+arr[2]

3. 점화식 

max(dp[i-1], dp[i-2] +arr[i], dp[i-3] +arr[i-1] +arr[i])

 

---

구현

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <algorithm>
using namespace std;

int main(){
    
    //1. 변수 설정
    int n;
    int arr[10001] = { 0, }; //포도주 양
    int dp[10001] = { 0, }; //인덱스 번째까지 포도주 최대 합
    scanf("%d", &n);

    for (int i = 1; i <= n; i++) {
        scanf("%d",&arr[i]);
    }

    //2. 초기식
    dp[1] = arr[1];
    dp[2] = arr[1] + arr[2];

    //3. 점화식
    for (int i = 3; i <= n; i++) {
        dp[i] = max(dp[i - 3] + arr[i - 1] + arr[i], max(dp[i - 1], dp[i - 2] + arr[i]));
       
    }

    printf("%d", dp[n]);
    
    return 0;   
}