[backjoon]14720 우유 도시 java

 

www.acmicpc.net/problem/14720

14720번: 우유 축제

그리디로도 풀 수 있다는데 DP로 풀었다.

일정한 순서가 있고(딸기 우유를 마셔야 초코 우유를 마실 수 있고, 초코 우유를 마셔야 바나나 우유를 마실 수 있고, 바나나 우유를 마신 다음에는 딸기 우유를 마셔야하는 것!)

이러한 순서가 있다보니, 내가 마신 종류별 우유의 갯수는 바로 전 순서와 같거나(내가 마실 우유의 위치가 아닌 경우) 전 순서보다 하나 더 많다.(마실 수 있는 우유의 위치인 경우)

-> 0 1 2 2 1 0 1 이 순서로 우유 거리가 늘어져있다고 생각하자.

처음엔 딸기 우유를 마셔야하고 0이기에 마실 수 있다. 딸기 우유 1이 된다. 그외의 값들은 이전의 값을 그대로 가져간다.

다음엔 1로 이미 딸기 우유를 마셨기에 초코 우유를 마실 수 있다. 초코 우유 1이 된다.

2로 초코 우유를 마셨기 때문에 바나나 우유를 마실 수 있다 바나나 우유 1이 된다.

2로 바나나 우유를 마실 수 있지만 규칙 상 이전에 바나나 우유를 마셨기 때문에 규칙에 맞지 않는다. 규칙 상 바나나 우유 다음에는 딸기 우유를 마셔야한다. 그렇기에 이전의 값을 가진다. 만약 이전의 딸기 우유보다 초코 우유 값이 클 수도 있기 때문에 미연 방지를 해줘야한다.

역시 1로 초코 우유를 마실 수 있지만 규칙 상 이전에 바나나 우유를 마셨기 때문에 규칙에 맞지 않는다. 규칙 상 바나나 우유 다음에는 딸기 우유를 마셔야한다. 그렇기에 이전의 값을 가진다.

0이기고 이전에 바나나 우유를 마셨기에 딸기 우유를 마실 수 있다. 딸기 우유의 수는 바나나 우유를 마신 이후가 되기 때문에 바나나 우유의 갯수보다 하나 많아야하기에 바나나 우유 2가 된다.

이를 이용하여 2차원 배열을 이용하여 코딩하면 된다.

 

import java.io.*;
import java.util.*;

class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());

		int[] map = new int[N];
		int[][] dp = new int[N][3];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			map[i] = Integer.parseInt(st.nextToken());
		}
		
		if(map[0] == 0) dp[0][0] = 1;
		
		for(int i = 1; i < N; i++) {
			int milk = map[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];
		}
		
		int max = Math.max(dp[N-1][0],Math.max(dp[N-1][1], dp[N-1][2]));
		System.out.println(max);
	}
		
}