https://www.acmicpc.net/problem/2156
2156번: 포도주 시식
효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고
www.acmicpc.net
문제는 백준 알고리즘 사이트에 있습니다~
먼저 분석부터 들어가봅시다! ㅎㅎ
조건 1. 잔을 선택하면 선택한 포도주는 모두 마신다.
조건 2. 연속으로 놓여있는 3개의 잔을 모두 마실 수 없다.
마실 수 있는 포도주의 최대 양을 구하는 문제입니다
조건 2에 의해 두번 연속으로 마시는건 가능하지만 3를 연속으로 마시는건 불가능하다는게 키포인트네요~
그럼 두번 연속으로 마시고 그 다음건 안마시면 됩니다 ㅎㅎ
진행을 구분해야할 필요가 있으니까 동적 계획법을 쓰면 되겠네요~
여기서 함정이 있는데요 그럼 2번 마시고 다음 포도주만 마시면 될까요?
조건 2에는 3개를 연속으로 마시면 안된다는 말만 있지 몇칸 이상 건너뛰면 안된다는 조건은 없습니다.
첫번째 포도주를 마시고 네번째 포도주를 마실수도 있고, 다섯번째 포도주를 마실수도 있다는점~!
유의하셔서 DP를 설계하면 답이 나옵니다
d[i][0] = wine[i] + d[i - 1][1]; // 연속으로 포도주를 마시는 경우
d[i][1] = wine[i] + max(p[0],...,p[i-2]); // 건너뛰고 i번째 포도주를 마시는 경우
조건에 조그만 함정이 있는 문제였습니다~
'Algorithms > Baekjoon Algorithms' 카테고리의 다른 글
| 알고리즘 설계 - 동적계획법 (Dynamic Programming) (0) | 2019.06.26 |
|---|---|
| 백준 알고리즘 2655 - 가장 높은 탑 쌓기 (0) | 2019.06.26 |
| 백준 알고리즘 2098 - 외판원 순회 (The Traveling Salesperson Problem) (0) | 2019.06.25 |
| 백준 알고리즘 2193 문제 - 이친수 (0) | 2019.06.22 |
| 알고리즘 글을 쓰려고 합니다. (0) | 2019.06.22 |
