21561 [C] 2156: 포도주 시식 처음에 점화식을 쉽게 찾았고 구현도 다른 DP 문제처럼 쉽게 되서 완전 쉽게 풀줄 알았다... 점화식은 쉽게 보면 근데 여기서 간과한 점이 다른 "계단 오르기"문제와의 차이점이 있다는 것인데 그건 바로 와인을 안마셔도 된다는 것이었다..! 예를 들어 (6) 100 100 1 1 100 100의 최대 포도주 양은 계단 오르기 문제에서는 301이지만 여기서는 400이 된다. 3번째와 4번째에서는 안마시는게 이득이다. 따라서 if(dp[i]=2) { dp[2]=dp[1]+arr[2]; cnt=2; //연속 두잔을 마심 max=dp[2]; } if(n==3) { if(arr[2]>arr[1]) dp[3]=arr[2]+arr[3]; else { dp[3]=arr[1]+arr[3]; cnt=1; } max=dp[3.. 2023. 7. 24. 이전 1 다음