반응형
시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 256 MB | 1319 | 346 | 276 | 32.281% |
문제
영학이는 딸기우유, 초코우유, 바나나우유를 좋아한다.
입맛이 매우 까다로운 영학이는 자신만의 우유를 마시는 규칙이 있다.
- 맨 처음에는 딸기우유를 한 팩 마신다.
- 딸기우유를 한 팩 마신 후에는 초코우유를 한 팩 마신다.
- 초코우유를 한 팩 마신 후에는 바나나우유를 한 팩 마신다.
- 바나나우유를 한 팩 마신 후에는 딸기우유를 한 팩 마신다.
저번 축제에서 수많은 우유를 마셨지만 더욱 우유에 갈증을 느낀 영학이는 우유 여행을 떠났다.
맛있는 우유를 찾아 떠난 영학이는 수많은 우유 가게로 둘러 쌓인 어느 도시에 도착했다.
이 도시는 정사각형 형태의 2차원 격자 모양으로 남북으로 N개, 동서로 N개, 총 N*N개의 우유 가게들이 있다.
영학이는 도시의 서북쪽 끝 (1, 1)에서 출발해서 동남쪽 아래 (N, N)까지 까지 가면서 우유를 사 마신다.
각각의 우유 가게는 딸기, 초코, 바나나 중 한 종류의 우유만을 취급한다.
각각의 우유 가게 앞에서, 영학이는 우유를 사 마시거나, 사 마시지 않는다.
So cooooool~한 영학이는 오직 동쪽 또는 남쪽으로만 움직이기 때문에 한 번 지나친 우유 가게에는 다시 가지 않는다.
영학이가 마실 수 있는 우유의 최대 개수를 구하여라.
입력
첫 번째 줄에는 우유 도시의 영역 크기 N이 주어진다. (1 ≤ N ≤ 1000)
두 번째 줄부터 N+1 번째 줄까지 우유 도시의 정보가 주어진다.
0은 딸기우유만을 파는 가게, 1은 초코우유만을 파는 가게, 2는 바나나우유만을 파는 가게를 뜻하며, 0, 1, 2 외의 정수는 주어지지 않는다.
출력
영학이가 마실 수 있는 우유의 최대 개수를 출력하시오.
예제 입력 1
4
0 1 2 2
1 1 1 1
2 2 2 2
0 0 1 0
예제 출력 1
5
예제 입력 2
5
0 1 0 0 0
1 2 1 1 1
2 0 1 2 0
0 0 0 0 1
1 1 1 1 2
예제 출력 2
9
코드
/*
우유 축제
DP
dp[m][n][k] : 좌표 (m, n)가게까지 k밀크를 마셨을 때 먹을 수 있는 우유의 최대 개수
*/
import java.io.*;
import java.util.*;
public class p14722 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int n = Integer.parseInt(br.readLine());
int[][] map = new int[n][n];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < n; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
int[][][] dp = new int[n][n][3];
if (map[0][0] == 0) {
dp[0][0][0] = 1;
}
// 가로 셋팅
for (int i = 1; i < n; i++) {
int milk = map[0][i];
dp[0][i][0] = milk == 0 ? dp[0][i - 1][2] + 1 : dp[0][i - 1][0];
dp[0][i][1] = milk == 1 && dp[0][i][2] < dp[0][i][0] ? dp[0][i-1][0] + 1 : dp[0][i-1][1];
dp[0][i][2] = milk == 2 && dp[0][i][0] < dp[0][i][1] ? dp[0][i-1][1] + 1 : dp[0][i-1][2];
}
// 세로 셋팅
for (int i = 1; i < n; i++) {
int milk = map[i][0];
dp[i][0][0] = milk == 0 ? dp[i-1][0][2] + 1 : dp[i-1][0][0];
dp[i][0][1] = milk == 1 && dp[i][0][2] < dp[i][0][0] ? dp[i-1][0][0] + 1 : dp[i-1][0][1];
dp[i][0][2] = milk == 2 && dp[i][0][0] < dp[i][0][1] ? dp[i-1][0][1] + 1 : dp[i-1][0][2];
}
for (int i = 1; i < n; i++) {
for (int j = 1; j < n; j++) {
int milk = map[i][j];
dp[i][j][0] = milk == 0
? Math.max(dp[i][j-1][2] + 1, dp[i-1][j][2] + 1)
: Math.max(dp[i][j-1][0], dp[i-1][j][0]);
dp[i][j][1] = milk == 1 && dp[i][j][2] < dp[i][j][0]
? Math.max(dp[i][j-1][0] + 1, dp[i-1][j][0] + 1)
: Math.max(dp[i][j-1][1], dp[i-1][j][1]);
dp[i][j][2] = milk == 2 && dp[i][j][0] < dp[i][j][1]
? Math.max(dp[i][j-1][1] + 1, dp[i-1][j][1] + 1)
: Math.max(dp[i][j-1][2], dp[i-1][j][2]);
}
}
System.out.println(Math.max(dp[n-1][n-1][0], Math.max(dp[n-1][n-1][1], dp[n-1][n-1][2])));
}
}
반응형
'알고리즘 > [ Baekjoon ]' 카테고리의 다른 글
[ BOJ ][JAVA][14888] 연산자 끼워넣기 (0) | 2021.05.06 |
---|---|
[ BOJ ][JAVA][14725] 개미굴 (0) | 2021.05.05 |
[ BOJ ][JAVA][14720] 우유 축제 (0) | 2021.05.05 |
[ BOJ ][JAVA][14719] 빗물 (0) | 2021.05.05 |
[ BOJ ][JAVA][14712] 넴모넴모 (0) | 2021.05.05 |