DP
-
[백준 2156] - [다이나믹프로그래밍] - 포도주 시식 (JAVA)알고리즘/다이나믹프로그래밍(Dynamic Programming) 2018. 12. 27. 13:33
문제 링크 : https://www.acmicpc.net/problem/2156 이 문제는 다이나믹 프로그래밍 (DP) 으로 접근 하면 된다. 다이나믹 프로그래밍에서 제일 중요한건 점화식이다. 같은 규칙으로 계산이 되고 그 규칙을 찾고 찾은 규칙에서 점화식을 구하면 문제는 아주 쉽게 풀린다. 모든 DP 문제는 점화식 구하는게 일이다. 이 문제에서 제공하는 조건은 두가지가 있다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 일단 첫번째 조건은 한 잔에 들어 있는 포도주를 찔끔찔끔 마실수 없다는걸 말하는 거고 두번째 조건은 연속으로 3잔을 마실수 없다는걸 말한다. 이 두번째 조건이 점화식을 구..