[ BOJ ][JAVA][14720] 우유 축제

www.acmicpc.net/problem/14720

14720번: 우유 축제

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	2207	1264	1088	60.918%

문제

영학이는 딸기우유, 초코우유, 바나나우유를 좋아한다.

입맛이 매우 까다로운 영학이는 자신만의 우유를 마시는 규칙이 있다.

1. 맨 처음에는 딸기우유를 한 팩 마신다.
2. 딸기우유를 한 팩 마신 후에는 초코우유를 한 팩 마신다.
3. 초코우유를 한 팩 마신 후에는 바나나우유를 한 팩 마신다.
4. 바나나우유를 한 팩 마신 후에는 딸기우유를 한 팩 마신다.

영학이는 우유 축제가 열리고 있는 우유거리에 왔다. 우유 거리에는 우유 가게들이 일렬로 늘어서 있다.

영학이는 우유 거리의 시작부터 끝까지 걸으면서 우유를 사먹고자 한다.

각각의 우유 가게는 딸기, 초코, 바나나 중 한 종류의 우유만을 취급한다.

각각의 우유 가게 앞에서, 영학이는 우유를 사마시거나, 사마시지 않는다.

우유거리에는 사람이 많기 때문에 한 번 지나친 우유 가게에는 다시 갈 수 없다.

영학이가 마실 수 있는 우유의 최대 개수를 구하여라.

입력

첫째 줄에 우유 가게의 수 N이 주어진다. (1 ≤ N ≤ 1000)

둘째 줄에는 우유 가게 정보가 우유 거리의 시작부터 끝까지 순서대로 N개의 정수로 주어진다.

0은 딸기우유만을 파는 가게, 1은 초코우유만을 파는 가게, 2는 바나나우유만을 파는 가게를 뜻하며, 0, 1, 2 외의 정수는 주어지지 않는다.

출력

영학이가 마실 수 있는 우유의 최대 개수를 출력하시오.

예제 입력 1

7
0 1 2 0 1 2 0

예제 출력 1

7

코드

/*
    우유 축제
    DP
    dp[n][milk] : n번째 가게까지 milk으유를 마셨을 때 먹을 수 있는 우유의 최대 개수
    dp[n][0] = (dp[n-1][2] + 1 or dp[n-1][0])
    -> 딸기우유 = 이전 가게까지 바나나 우유를 마셨을 때의 최대 개수

    dp[n][1] = (dp[n-1][0] + 1 or dp[n-1][1])
    -> 딸기우유 = 이전 가게까지 바나나 우유를 마셨을 때의 최대 개수

    dp[n][2] = (dp[n-1][1] + 1 or dp[n-1][2])
    -> 딸기우유 = 이전 가게까지 바나나 우유를 마셨을 때의 최대 개수

    milk == 1 && dp[i][2] < dp[i][0]
    -> 아무리 이전 순서인 우유가 있어도 현재 딸기우유를 하나 먹을 때가 바나나 우유를 먹은것보다 항상 값이 커야 순서가 맞는 것이다.

    milk == 2 && dp[i][0] < dp[i][1]
    -> 아무리 이전 순서인 우유가 있어도 바나나 우유를 먹을 때가 딸기우유를 먹을때보다 항상 값이 커야 순서가 맞는 것이다.
*/
import java.io.*;
import java.util.*;
public class p14720 {
    static int[][] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        dp = new int[n][3];

        // 가장 먼저 딸기우유를 마시므로 arr이 0일 경우에만 dp를 1로 만들어준다.
        if (arr[0] == 0) {
            dp[0][0] = 1;
        }

        for (int i = 1; i < n; i++) {
            int milk = arr[i];

            dp[i][0] = milk == 0 ? dp[i-1][2] + 1 : dp[i-1][0];
            dp[i][1] = milk == 1 && dp[i][2] < dp[i][0] ? dp[i-1][0] + 1 : dp[i-1][1];
            dp[i][2] = milk == 2 && dp[i][0] < dp[i][1] ? dp[i-1][1] + 1 : dp[i-1][2];
        }
        System.out.println(Math.max(dp[n-1][0] , Math.max(dp[n-1][1], dp[n-1][2])));
    }
}