Algo
백준 14722 우유 도시
문제링크: 여기
회고
DP 3차원 배열 문제였다. dp 문제를 풀 때는 앞의 상황에서 O/X에 따라 그 다음 선택에 영향을 주되, 각각의 상태 자체는 유지 되는 게 DP 문제의 특징이라는 걸 또 느꼈다.
이 문제에서 중요했던 지점은, 2차원 배열로 모든 경우의 수를 따져볼 수 없다는 점에서 기인된다는 것이다. i, j에서 마실 수 있는 우유가 1이라고 가정한다면, 위(i-1, j) 또는 옆(i, j-1)에서 0을 마신 경우와 0이 아닌 우유를 마신 경우로 분류된다. 둘 중 어느 것이 항상 더 우위라고 판단할 수 없다. 따라서, 특정 지점(i, j)에서 딸기(0), 초코(1), 바나나(2) 우유를 마신다고 할 때 어디서 오는 게 더 이득일지 모르니 3차원 배열로 변환해야 한다.
한가지 더 중요했던 지점은,
- 일단 안 마시는 경우를 디폴트로 지정해야 한다. 그 이유는 지금 안 마시는 게 미래에 더 이득일 수도 있으니 미리 고려한다.
- 현재 마신 우유가 0이라면, 이전에 (위 또는 옆) 아무것도 안 마신 상태이거나 (0개), 그 전에 바나나(2)를 마셨어야 한다.
- 현재 마신 우유가 0이 아니면, 초코(1)일 때는 딸기(0)을 마셨어야 했고 바나나(2)일 때는 초코(1)을 마셨어야 한다.
- 이때 무작정 dp[i][j][current] = dp[i][j][prev]+1; 이 아니다.
- 현재 (i,j)칸에 우유를 안 마시고 왔을 때랑, 지금 칸과 순서가 맞아 우유를 한잔 더 마실 수 있는 경우를 비교해야 한다.
- 따라서 dp[i][j][current] = Math.max(dp[i][j][current], getPrev+1);
개인적으로 3차원 dp를 연습하기에 가장 좋은 문제라는 생각이 들었다.
고민했던 흔적
딸기 > 초코 > 바나나 > 딸기 ..
0 1 2 0 1 2
n xn 우유 가게
(1,1) -> (N, N) 출발점과 목적지가 정해져있음
마시거나 안 마시거나
동, 남으로만 움직임
i, j 기준
i+1, j
i, j+1
n 1000
0 1 2 2
1 1 1 1
2 2 2 2
0 0 1 0
0행과 0열은 일단 채울 수 있음 전부 동 아님 전부 남으로만 이동하는 경우임
dp[][]: 여태 먹은 우유 개수
num[][]: 가장 최근에 그 자리에 먹는 우유 번호
i, j를 구한다고 치면
(위에서 올때) map[i][j] = (num[i-1][j] + 1) % 3 (그 다음에 먹을 우유 번호이면)
=> 맞으면 dp[i-1][j] + 1 이 들어감
=> 아니면 -1
(옆에서 올때) map[i][j] = (num[i][j-1] + 1) % 3 (그 다음에 먹을 우유 번호이면)
=> 맞으면 dp[i][j-1] + 1이 들어감
=> 아니면 -1
둘 다 -1이면 (어느쪽에서 와도 못 마심)
- dp[i][j-1], dp[i-1][j] 중에 더 크거나 같은 값을 dp에 저장
- 더 큰 쪽에서 왔을 때 마지막으로 먹은 우유 번호 넣기
만약 하나만 -1이면
- -1이 아닌 쪽에서의 dp+1 && 그 자리서 먹은 map[i][j]
만약 둘 다 -1이 아니면
- dp+1한 값이 더 큰 쪽을 따른다
---
예외 상황의 존재:
i-1, j -> 5개를 마신 상태 & 마지막우유 = 1 (초코)
i, j-1 -> 4개를 마신 상태 & 마지막우유 = 2(바나나)
i, j가 0번일 때의 정답은? 2가지 경우를 다 저장해둬야 한다. 미래에 1을 유지한 게 나았을 수도 2를 먹은 게 나았을 수도 있다.
근데? 우리의 논리를 따르면 i-1, j까지 먹는데 걸린 우유의 개수가 5개니까 거기서 오는 걸로 정해버림
따라서 dp[i][j] = value였으면 dp[i][j][state] = value로 변경 필요
이때 state는 이 칸에 도착했을 때 마지막으로 마신 우유의 종류
dp[i][j][0]: 마지막으로 0을 먹었을 때의 최대 개수
---
/**
* 현재 위치에서 우유를 안 마신다고 가정하면:
* - 이전 칸 i-1, j 또는 i, j-1 값을 그대로 계승함
*
* 현재 위치에서 우유를 마신다고 가정하면:
* 1. current == 0 인 경우: 이전에 아무것도 안 마셨거나(0개), prev = 2였어야 함
* 2. current > 0 인 경우: prev = current -1 이어야 함
*
* ++ 지금 안 마시는 게 이득일 수 있음
*/