하루일문
[백준] 2156번 포도주(파이썬) 본문
문제
2156번: 포도주 시식
효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규
www.acmicpc.net
코드
n = int(input())
grape = [0] + [int(input()) for _ in range(n)]
drink = [0] * (n+1)
drink[1] = grape[1]
# n==1이면 drink[2]가 없으니 인덱스 에러가 남
if n != 1:
drink[2] = sum(grape[1:3])
for i in range(3, n+1):
# 연속을 마시지 않을 때 - drink[i-1]
# drink[i-2]을 마실 때
# drink[i-2]을 마시지 않을 때
drink[i] = max(drink[i-1], drink[i-2] + grape[i], drink[i-3] + grape[i-1] + grape[i])
print(drink[n])해설
계단오르기와 비슷한 유형의 DP문제이다. 아래 참고로 링크를 걸어두겠다.
다른 점이 있다면, 와인을 연속으로 마시지 않아도 된다는 점이다. 그렇기 때문에 먹지 않을때 drink에 수를 넣어주기 위해
drink[i-1]
를 넣어주어야 한다. 넣지 않는다면 아래 유형에서 틀리게 된다.
6
1000
1000
1
1
1000
1000
먼저 점화식을 위해 drink[1], drink[2]를 채워주고, 연속으로 마시지 않을때와 선택 부분을 건너뛰고 마실때, 선택부분을 마실때 상황을 비교하며 제일 큰 값을 drink[i]에 넣어준다.
계단오르기 풀이
[백준] 2579번 계단 오르기(파이썬)
문제 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계
support-u-oneday.tistory.com
'algorithm > baekjoon' 카테고리의 다른 글
| [백준] 2776번 암기왕(python) (0) | 2023.04.20 |
|---|---|
| [백준] 1003번 피보나치 함수(파이썬) (0) | 2023.04.19 |
| [백준] 1075번 나누기 (파이썬) (0) | 2023.04.17 |
| [백준] 7569번 토마토(파이썬) (1) | 2023.04.16 |
| [백준] 9663번 N-Queen(파이썬) (0) | 2023.04.15 |