14720. 우유 축제

문제링크 : https://www.acmicpc.net/problem/14720

< 입력 >

우유 가게 수 n

n개의 가게 정보 ( 0 : 딸기우유, 1 : 초코우유, 2 : 바나나우유 )

< 출력 >

최대로 마실 수 있는 우유의 개수

< 풀이 >

역시 단순한 dp 문제이다.

0(딸기우유)번 가게일 경우 이전의 2(바나나우유)번 가게의 값 중 Max +1을 하고

1(초코우유)번 가게는 이전의 0(딸기우유)번 가게의 값 중 Max +1,

2(바나나우유)번 가게는 이전의 1(초코우유)번 가게의 값 중 Max +1을 하면 된다.

여기서 주의해야할 예외는 1. 맨 처음에는 딸기우유를 한 팩 마신다. 이다.

즉, 1과 2가 나오더라도 0이 나오기 전이라면 값을 갱신해서는 안된다.

예외처리를 해줘야 하는 경우는 2가지이다.

1) 0이 나왔을 때만 dp값을 1로 바꿔준다.

2) 1혹은 2가 나왔을 때 이전의 값을 확인하게 된다. 이 때, 이전의 dp값이 0이 아닐 경우만 확인한다.

---

- 소스 코드 -

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int main(void){
    int arr[1002] = {0}; // 무슨 우유인지 받을 배열
    int dp[1002] = {0};
    int n;
    cin >> n;
 
    for (int i = 0; i < n; i++){
        scanf("%d", &arr[i]);
    }
    for (int i = 0; i < n; i++){
        if (dp[i] == 0 && arr[i] == 0){
            dp[i] = 1;
            // 가장 먼저 딸기우유를 마셔야 한다. (예외1)
            // 따라서 dp가 0이지만 arr도 0일 경우만 1로 만들어준다.
        }
        for (int j = i - 1; j >= 0; j--){
            if (dp[j] != 0){
            // 가장 먼저 딸기우유를 마셔야한다.(예외1)
            // 따라서 아무리 이전 순서인 우유가 있어도 딸기우유가 나오기 전에는
            // 먹지 못한다.(예외2)
                if (arr[i] == 2){
                    if (arr[j] == 1){
                        dp[i] = max(dp[i], dp[j] + 1);
                    }
                }
                else if (arr[i] == 1){
                    if (arr[j] == 0){
                        dp[i] = max(dp[i], dp[j] + 1);
                    }
                }
                else{
                    if (arr[j] == 2){
                        dp[i] = max(dp[i], dp[j] + 1);
                    }
                }
            }
        }
    }
    int result = 0;
    for (int i = 0; i < n; i++){
        // printf("%d ", dp[i]);
        result = max(result, dp[i]);
    }
    // cout << endl;
    cout << result << endl;
}

---