앗! 광고가 차단되었어요!
글 내용이 방문자께 도움이 되었다면, 광고 차단 프로그램 해제를 고려해주세요 😀.
2156번: 포도주 시식
효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규
www.acmicpc.net
오늘은 포도주를 시음해보자.
이 문제는 간단한 점화식으로 해결할 수 있다.
DP배열[i]의 의미는 i번째 포도주까지 고려했을 때, 최대한 마실 수 있는 양을 의미하게 된다.
그러면 DP[i]는 3가지 경우에 의해 결정된다.
1) 포도주를 안마신다.
☞ DP[i-1]
2) 포도주를 마시되, 바로 이전 포도주도 마셨다. 그러면 i-2번째 포도주는 마시지 않은 것이다.
☞ 포도주[i] + 포도주[i-1] + DP[i-3]
3) 포도주를 마시되, 바로 이전 포도주를 마시지 않았다.
☞ 포도주[i] + DP[i-2]
'알고리즘 노트' 카테고리의 다른 글
| 수학 시리즈: 11051번 이항 계수 2, 1676번 팩토리얼 0의 개수, 2004번 조합 0의 개수 Hint (0) | 2020.11.28 |
|---|---|
| 1541번: 잃어버린 괄호 (0) | 2020.11.27 |
| 11053번: 가장 긴 증가하는 부분 수열 Hint (0) | 2020.10.27 |
| 2580번: 스도쿠 Hint (0) | 2020.10.27 |