백준 14722 - 우유 도시

Java

14722 번 - 우유 도시

문제

접근 방법

n이 최대 1000이며, 그래프 탐색이므로 시간초과가 나기 쉽다.
따라서 dp를 사용하여 해결한다.

dp는 n x n 크기의 배열에 현재 마실 우유의 상태를 나타내는 상태를 추가하여,
3차원 배열로 나타낸다.
즉, 다음과 같다.

dp[m][n][milk] = 좌표 (m,n) 가게까지 어떤 우유를 마셨을 때 우유의 최대 개수

이후 점화식은 다음과 같다. 현재 마실 milk가 curMilk, 이전 순서의 milk가 lastMilk 일 때,

1. 현재 y,x 좌표의 위치에서 현재 우유를 마실 때
   dp[y][x][milk] = dp[y - 1][x][lastMilk] + 1 과 dp[y][x - 1][lastMilk] + 1 중 큰 것을 선택한다.
2. 현재 y,x 좌표의 위치에서 현재 우유를 마시지 않으면
   dp[y][x][milk] = dp[y - 1][x][lastMilk] 과 dp[y][x - 1][lastMilk] 중 큰 것을 선택한다.

위 점화식을 이용하면 입력값의 첫번째는 0,0이므로 이전 y - 1, x - 1이 음수가 된다.
따라서 편의를 위해 배열의 크기를 map[n + 1][n + 1]로 두어 0행 0열을 패딩으로 둔다.

또한 딸기우유 => 초코 우유 => 바나나 우유 순으로 마시므로 추가로 조건문을 설정한다.
초코우유와 바나나 우유의 경우 이전 순서의 우유를 마셨는지 체크하는 로직을 두어 확인한다.

코드

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

public class Main {
	static int n, result;
	static int[][] map;
	static int[][][] dp;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk;
    	n = stoi(br.readLine());

    	map = new int[n + 1][n + 1];

    	for(int i = 1; i <= n; i++) {
    		stk = new StringTokenizer(br.readLine());
    		for(int j = 1; j <= n; j++) {
    			map[i][j] = stoi(stk.nextToken());
    		}
    	}
    	dp = new int[n + 1][n + 1][3];
    	int curN;
    	// init 종료
    	// dp 시작

    	// i, j가 1 이상일 때 : 0행 0열
    	for(int i = 1; i <= n; i++) {
    		for(int j = 1; j <= n; j++) {
    			curN = map[i][j];		// 현재 칸에서 마실 우유

				// 딸기 우유를 먹을 차례일 때
				dp[i][j][0] = curN == 0 ?
						Math.max(dp[i - 1][j][2], dp[i][j - 1][2]) + 1 :
						Math.max(dp[i - 1][j][0], dp[i][j - 1][0]);
				// 초코 우유를 먹을 차례일 때
				dp[i][j][1] = curN == 1 && dp[i][j][0] > dp[i][j][1] ?
						Math.max(dp[i - 1][j][0], dp[i][j - 1][0]) + 1 :
						Math.max(dp[i - 1][j][1], dp[i][j - 1][1]);
				// 바나나 우유를 먹을 차례일 때
				dp[i][j][2] = curN == 2 && dp[i][j][1] > dp[i][j][2] ?
						Math.max(dp[i - 1][j][1], dp[i][j - 1][1]) + 1 :
						Math.max(dp[i - 1][j][2], dp[i][j - 1][2]);
    		}
    	}

    	for(int i = 0; i <= 2; i++) {
    		result = Math.max(result, dp[n][n][i]);
    	}

    	System.out.println(result);
    	br.close();
	}


	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

개선할 점