Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
Tags
- greedy
- BASIC
- BFS
- php
- DP
- 종만북
- 따라하며 배우는 C언어
- 생활코딩
- Python
- server
- Cleancode
- web
- C언어
- C
- Math
- BOJ
- dfs
- 인프런
- 따라하면서 배우는 C언어
- Algorithm
- 백준
- udemy
- graph
- JavaScript
- programmers
- sorting
- Algospot
- 따배씨
- 정수론
- String
Archives
- Today
- Total
몽상실현개발주의
[BOJ] 2156 / 포도주 시식 / Python 본문
[BOJ] 2156 / 포도주 시식 / Python
풀이
주어진 조건에 대한 규칙을 배열을 이용하여 찾을 수 있는 문제이다.
i 번째 포도주 선택에 대한 경우의 수는 다음과 같다.
~ i-3 | i-2 | i-1 | i |
~ | O | O | X |
~ | O | X | O |
~ | X | O | O |
위의 세 경우 중 가장 양이 커질 경우를 선택하면 된다.
A = dp[i-1]
B = wine[i] + dp[i-2p]
C = wine[i] + wine[i-2] + dp[i-3]
dp[i] = max(A, B, C)
N = int(input())
wine = [0] * N
dp = [0] * N
for i in range(N):
wine[i] = int(input())
dp[0] = wine[0]
if N > 1:
dp[1] = wine[0] + wine[1]
if N > 2:
dp[2] = max(dp[1], wine[2]+dp[0], wine[2]+wine[1])
if N > 3:
for i in range(2, N):
a = dp[i-1]
b = wine[i] + dp[i-2]
c = wine[i] + wine[i-1] + dp[i-3]
dp[i] = max(a, b, c)
print(dp[-1])
'Algorithm PS > BOJ' 카테고리의 다른 글
[BOJ] 11055 / 가장 큰 증가 부분 수열 / Python (0) | 2021.05.12 |
---|---|
[BOJ] 11053 / 가장 긴 증가하는 부분 수열 / Python (0) | 2021.05.12 |
[BOJ] 9465 / 스티커 / Python (0) | 2021.05.12 |
[BOJ] 2193 / 이친수 / Python (0) | 2021.05.11 |
[BOJ] 11058 / 오르막 수 / Python (0) | 2021.05.11 |
Comments