(BOJ 19645 햄최몇?) DP 필요한 정보 파악/점화식 [Knapsack류]

Sol 1, Sol 2 시행착오를 통해 배운 점 기록.

 

 

 

 

Sol 1) DP[i][person] : i번째 햄버거를 먹을 때, person이 먹은 경우; 효용을 (p0, p1, p2)로 저장

DP[i][0] = DP[i-1][0, 1, 2] 중, p0 + ham[i] 한게 다른 선배들보다 작다는 조건을 만족하는 max 효용 값;
DP[i][0] = max(DP[i-1][p]) where p = 0~2 and DP[i-1][p][0] + ham[i] <= DP[i-1][p][1] and DP[i-1][p][1]

왜 틀렸는가? → DP[i-1]엔 3가지 선택지가 있는데, 그 중 p0 + ham[i] 가 "가장 큰 값"을 선택한다는 점.
이 문제는 중간 단계에서, "최선이 아닌 정보가 필요한 경우"가 있음

ex) 20 15 4 5 10
4번째 햄버거를 먹는데, DP[4][0]은 세 가지 선택지 존재 : (9, 15, 20), (5, 19, 20), (5, 15, 24)
여기서 p0가 가장 큰 (9, 15, 20)을 선택하는게 local 입장에선 맞아 보이지만, 마지막 10짜리 햄버거를 못먹음.
반면에, (5, 19, 20)을 고르면 마지막 10짜리 햄버거 먹고 최종적으로 (15, 19, 20)이 가능.

---

Sol 2) 선배들의 정보를 담고, 최선이 아닌 정보도 저장하는 방법 = 모든 효용의 경우의 수를 다 따져보기
DP[p0][p1][p2] : (p0, p1, p2)의 효용이 가능하면 True, 아니면 False 저장
DP[p0][p1][p2] = DP[p0-h][p1][p2] || DP[p0][p1-h][p2] || DP[p0][p1][p2-h]

왜 틀렸는가? → 어떤 햄버거를 먹을지 어떻게 정함? 매번 N개 햄버거 각각 먹는 경우 따지면, 
먹은 햄버거 다시 먹는 중복 생길수도. 즉, 어떤 햄버거까지 먹었는지 정보도 필요함.

---

Sol 3) 선배들의 정보 + 최선이 아닌 정보 저장 + 어떤 햄버거까지 먹었나
DP[i][p0][p1] : i번째 햄버거까지 먹었을 때, 막내의 효용 p0와 둘째 선배의 효용 p1이 가능하면 True

(최고참 선배의 효용은 'i까지의 햄버거 합 - p0 - p1' 으로 구하기 가능)
★ 이때, 막내의 효용이 선배들보다 작아야 한다는 조건을 따지지 않는다

DP[i][p0][p1] = DP[i-1][p0][p1] || DP[i-1][p0 - ham[i]][p1] || DP[i-1][p0][p1 - ham[i]]
(첫번째 term은 최고참 선배가 먹는 것, 둘째는 막내가 먹는 것, 셋째는 둘째 선배가 먹는 것)

즉, 어떻게든 햄버거를 먹어서 해당 효용 조합 (p0, p1, Sum[i] - p0 - p1)이 만들어지는지 먼저 체크!

 

초기화 : 첫번째 버거를 첫째/둘째/셋째가 먹는 경우 총 3가지;

이후엔 i=1~N-1 까지 돌면서 테이블 전체 체크 (테이블 길이 = maxA * N / 3)

DP를 완성하면, DP[N-1]을 돌면서 막내의 효용이 선배들보다 작은 경우만 체크. 이 중, 막내 효용 max 구하기
→ 햄버거를 순서대로 먹는 모든 경우의 수 다 따짐 = 가능한 모든 효용의 조합을 체크 
그 중 constraint 만족하는 것만 뽑아서 체크

 

---

[생각/구현 어려웠던 부분]
- 문제를 잘못 이해함. 막내인 '길원'이만 순서 지키면 됨; 둘째 선배는 첫째 선배보다 효용 작아야한다는 조건 없음

- DP 문제에서 꼭 필요로 하는 정보가 있음. 이를 파악하는게 핵심 (많은 문제풀이를 통해 유사한 경험 쌓는게 핵심)
1. 선배들의 정보가 꼭 필요한데, 어떤 식으로 넘기지?
2. 최선이 아닌 정보도 매번 저장해야 함. 도대체 어떻게?
(최선의 정보만 저장하면, optimal substructure가 안 만들어짐 → knapsack 문제 특. 전체 문제의 최적해 못구함)
3. 지금까지 먹은 버거?

결론을 내리면,

지금까지 먹은 버거 i를 기점으로,

세 사람의 효용 상태를 저장해야 하며,

최대 값이 아닌 경우도 따질 수 있게 해야함.

 

각 효용이 가능한지 불가능한지 파악하면, 막내 효용이 작아야 한다는 조건은 나중에 체크할 수 있으니,

결국 True/False 값만 저장하면 됨 

 

[개선 할만한 점]
★ 'Knapsack' 문제임을 느끼기.

3가지 배낭에 물건을 나눠 담아서 가치(효용)가 max가 되도록 해야함.
근데, '막내의 효용이 선배보다 작아야 함'이라는 constraint가 하나 붙어있는 문제
=> value가 max가 되도록 물건을 담는데, weight라는 조건이 붙은 knapsack이랑 비슷.
'최선이 아닌 정보'를 저장해야한다는 접근이 여기서 유래되는 듯.

 

 

glanceyes.tistory.com/62?category=969667

BOJ 백준 19645번 햄최몇?