문제링크 : https://www.acmicpc.net/problem/2156
2156번: 포도주 시식
효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규
www.acmicpc.net
작성코드
해설
이 문제는 2579 계단 오르기 문제와 거의 동일한 문제이다.
https://yellowtail2357.tistory.com/37
[백준] 2579 계단 오르기 (python 파이썬)
문제링크 : https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가
yellowtail2357.tistory.com
※ 주의점
다른 점은 2579 계단 오르기의 경우 마지막 계단을 밟는것이 필수인데
2156 포도주 시식의 경우 마지막 포도주를 마시는 것이 필수가 아니다.
이를 생각하여 코드를 작성할 때 max()에 이번 포도주를 선택하지 않는 경우(dp[i-1])을 넣어주어야만 한다.
포도주 선택의 룰은 다음과 같다
- 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
- 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.
가장 많은 양의 포도주를 마셔야 하므로
max() 값으로 위 룰을 넣어주어 작성한다.
연속으로 놓여있는 3잔을 모두 마실 수 없기 때문에
나열된 포도주를 먹을 때
3가지 경우의 수가 생긴다
현재 포도주 선택 + 전 포도주 선택 + 전전 포도주 비선택인 이전까지의 최대값
현재 포도주 선택 + 전 포도주 비선택 + 전전 포도주 선택인 이전까지의 최대값
현재 포도주 비선택, 전 포도주 선택인 이전까지 최대값
이 경우의 수들 중 최대값을 선택하면 가장 많은 양의 포도주를 먹는 것과 같다.
이를 코드로 작성하면 아래와 같은 형태가 된다.
이 코드를 사용하기 위해서 미리 dp[0], dp[1], dp[2]는 작성해준다.
결과 값 출력은
print(dp[N-1]) 혹은 print(max(dp))를 해주면 된다.
'백준 > Python' 카테고리의 다른 글
| [백준] 11054 가장 긴 바이토닉 부분 수열 (python 파이썬) (0) | 2022.12.07 |
|---|---|
| [백준] 11053 가장 긴 증가하는 부분 수열 (python 파이썬) (0) | 2022.12.05 |
| [백준] 2579 계단 오르기 (python 파이썬) (0) | 2022.12.01 |
| [백준] 26073 외로운 곰곰이는 친구가 있어요 (python 파이썬) (0) | 2022.11.30 |
| [백준] 26072 곰곰이와 시소 (python 파이썬) (0) | 2022.11.28 |