[백준] 14720. 우유 축제

문제 링크

[백준] 14720. 우유 축제

풀이 과정

동적 계획법 문제입니다.

가게 정보로 딸기우유는 0, 초코우유는 1, 바나나우유는 2로 주어집니다. 현재 i번째 가게까지 이동했을 때 각각의 우유를 마실 수 있는 최대 개수를 지정하는 배열 dp를 선언합니다.

1. 가게에서 파는 우유의 정보를 stores 배열에 담았을 때, i번째 우유 가게에서 파는 우유의 종류 now는 stores[i]가 된다.
2. 이전 가게, 즉 (i-1)번째 우유 가게에서 파는 우유의 종류 prev는 now-1로 설정한다. 이 때, prev가 -1이 될 수 있으니 2로 적절하게 조정한다.
3. dp[now]를 아래와 같은 식으로 도출할 수 있다.

$$dp[now]=Max(dp[now], dp[prev]+1) $$

예를 들어, i번째 우유 가게에서 딸기우유(0)를 판다고 가정하면, dp[0] = Max(dp[0], dp[2] + 1)이 됩니다. 즉, 기존에 딸기우유를 마신 최대 횟수 dp[0]과, 이전까지 바나나우유(2)를 마신 경우에 현재 딸기우유를 추가로 마신 값 dp[2]+1을 비교해 더 큰 값으로 대체하게 됩니다.

마지막 우유 가게까지 위 과정을 마쳤다면, 아래 세 경우 중 가장 큰 값을 답으로 채택할 수 있습니다.

• 마지막으로 딸기우유(0)를 마신 경우의 최대 우유 개수 dp[0]
• 마지막으로 초코우유(1)를 마신 경우의 최대 우유 개수 dp[1]
• 마지막으로 바나나우유(2)를 마신 경우의 최대 우유 개수 dp[2]

코드

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] stores = new int[N];
        int idx = 0;
        int answer = 0;
        int[] dp = new int[3];

        for (int i = 0; i < N; i++) stores[i] = sc.nextInt();

        while (stores[idx] != 0) idx++;

        dp[0] = 1;

        for (int i = idx + 1; i < N; i++) {
            int now = stores[i];
            int prev = now - 1 < 0 ? 2 : now - 1;

            if (dp[prev] == 0) continue;

            dp[now] = Math.max(dp[now], dp[prev] + 1);
        }

        for (int i = 0; i < 3; i++) {
            answer = Math.max(answer, dp[i]);
        }

        System.out.println(answer);
    }
}