백준 2156번 문제입니다. (solved.ac)기준 실버 1 문제입니다.
아래에 있는 백준 2579번 계단 오르기 문제와 굉장히 유사한 문제입니다.
[백준] 2579번 계단 오르기(다이나믹 프로그래밍)(DP)(Python)
문제 접근
포도주를 마시는데에는 두 가지 규칙이 존재합니다.
1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.
동적계획법(다이나믹 프로그래밍)으로 접근하였고
wine 이라는 리스트를 만들어 wine[n]에는 n번째 포도주 잔에 있는 포도주 양을 담도록 하고
d라는 리스트를 만들어 d[n]에는 n번째 포도주를 먹거나 먹지 않을 때 최대 포도주의 양이 들어갑니다.
d[n]에서 n번째 포도주를 먹을 경우 최대 포도주의 양은 아래 두 경우 중 더 큰 값이 됩니다. (연속으로 3잔을 마실 수 없음)
# n번째 전전전의 위치까지 마실 수 있는 포도주양의 최댓값(d[n-3]) + n번째 전에 있는 포도주의 양(wine[i-1]) +
# n번째에 있는 포도주의 양(wine[n])
d[n-3] + wine[n-1] + wine[n]
# n번째 전전의 위치까지 마실 수 있는 포도주양의 최댓값(d[n-2]) + n번째에 있는 포도주의 양(wine[n])
d[n-2] + wine[n]
d[n]에서 n번째 포도주를 먹지 않을 경우 아래와 같이 d[n-1]이 최대 포도주의 양이 됩니다.
# n번째 전의 위치까지 마실 수 있는 포도주 양의 최댓값(d[n-1])
d[n-1]
따라서 d[n]의 값은 위의 3가지 경우중 최댓값이 됩니다.
d[n] = max(d[n-3] + wine[n-1] + wine[n], d[n-2] + wine[n], d[n-1])
만약 d[n]을 구할 때 n번째 포도주를 마시지 않을 경우를 고려하지 않는다면 예제 1번 기준으로
d리스트에는 [0, 6, 16, 23, 33, 32]가 들어가게 됩니다.
n번째 포도주를 마실 경우를 고려한다면
d리스트에 [0, 6, 16, 23, 28, 33, 33]가 들어가게 됩니다.
잘 이해가 되시지 않는다면 백준 질문글 중 자세한 답변을 해주신 분이 계셔서 링크를 첨부해 두겠습니다.
https://www.acmicpc.net/board/view/60664
정답 코드
n = int(input())
# 인덱스 관리가 쉽도록 맨앞을 0으로 wine[0] = 0
# 따라서 첫번째 포도주의 양은 wine[1]
wine =[0]
d = [0] * (n+1)
for _ in range(n) :
wine.append(int(input()))
d[1] = wine[1]
if n >= 2 :
d[2] = wine[1] + wine[2]
for i in range(3, n+1) :
d[i] = max(d[i-3] + wine[i-1] + wine[i], d[i-2] + wine[i], d[i-1])
print(d[n])
'알고리즘 문제풀이[Algorithm]' 카테고리의 다른 글
[백준] 1753번 최단경로(다익스트라 알고리즘)(Python - 파이썬) (0) | 2022.02.22 |
---|---|
[백준] 15829번 Hashing(Python - 파이썬) (0) | 2022.02.19 |
[백준] 1932번 정수 삼각형(다이나믹 프로그래밍)(DP)(Python - 파이썬) (0) | 2022.02.14 |
[백준] 11053번 가장 긴 증가하는 부분 수열(LIS)(DP)(Python - 파이썬) (0) | 2022.02.13 |
[백준] 2869번 달팽이는 올라가고싶다(수학)(Python - 파이썬) (0) | 2022.02.12 |
최근댓글