알고리즘/백준
[백준/Swift] 2156번: 포도주 시식
녕이
2023. 2. 20. 15:57
728x90
https://www.acmicpc.net/problem/2156
2156번: 포도주 시식
효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규
www.acmicpc.net
연속 3잔 모두 마실 수 없음
최대한 많은 양의 포도주 마시기. 최대양 출력!
주의할 것은 연속 3잔은 마실 수 없다는 것!
i번째까지 마셨을 때, 최대양을 구하면서 진행하기
4번째까지 왔다고 해보자.
4번 잔을 마시는 경우
- dp[1] + 3번 잔 + 4번 잔 (3 연속피하기)
- dp[2] + 4번 잔 (3 연속피하기)
4번 잔을 마시지 않는 경우 -> dp[3]
import Foundation
//input
let n = Int(readLine()!)!
var arr = [0]
var dp = [Int](repeating: 0, count: 10002)
for _ in 0..<n {
arr.append(Int(readLine()!)!)
}
var answer = 0 //max value
//dp[i]는 i번째까지 포도주를 마신 최대양
dp[1] = arr[1]
if n > 1 {
dp[2] = arr[1] + arr[2]
}
if n > 2 {
for i in 3...n {
dp[i] = max(dp[i-3] + arr[i-1] + arr[i], dp[i-2] + arr[i], dp[i-1])
}
}
print(dp[n])
헷갈리는 문제였다..
728x90