[Swift 알고리즘] 백준 BOJ - 2156 포도주 시식

안녕하세요. 개발 중인 정주입니다.

 

오늘은 "백준 BOJ - 2156 포도주 시식" 문제를 풀었습니다.

 

---

Github

GitHub - jeongju9216/SwiftAlgorithm: 스위프트 알고리즘

 

문제 링크

2156번: 포도주 시식

 

---

풀이

이번 문제는 DP를 이용한 문제입니다.

 

포도주를 마시는 경우와 마시지 않는 경우의 최대값을 선택하면 됩니다.

 

잔이 1개일 때는 무조건 마시는 것이 최대입니다.

잔이 2개일 때도 두 잔 모두 마시는 것이 최대입니다.

 

포도주가 세 잔이 연속으로 있을 때 발생할 수 있는 시나리오는 세 가지입니다.

1번	2번	3번
O	O	X
O	X	O
X	O	O

 

이 세 개의 시나리오 중 최대를 선택하면 되는데요.

1번과 2번을 마시는 시나리오는 dp[i-1]과 같고 1번을 마시고 2번을 마시지 않는 시나리오는 dp[i-2]와 같습니다.

따라서 1번 시나리오는 dp[i-1], 2번 시나리오는 dp[i-2] + 3번 포도주로 표현할 수 있습니다.

 

1번을 마시지 않고 2번, 3번을 마시는 경우는 어떻게 표현이 가능할까요?

바로 dp[i-3] + 2번 포도주 + 3번 포도주입니다.

dp[i-3]인 경우는 1번 포도주를 마시지 않는다면 이전 포도주를 마시는 것이 항상 최대이기 때문입니다.

 

위 세 가지 중 최대를 저장하며 포도주 잔 수만큼 반복하면 결과를 얻을 수 있습니다.

 

---

전체 코드

//2156 포도주 시식
import Foundation

let input = Int(readLine()!)!
var wines: [Int] = []
for _ in 0..<input {
    let wine = Int(readLine()!)!
    wines.append(wine)
}

var dp: [Int] = [0, wines[0]]
if input >= 2 {
    dp.append(dp[1] + wines[1])
}

if input >= 3 {
    for i in 3...input {
        var maxInput = max(dp[i-1], dp[i-2] + wines[i-1])
        maxInput = max(maxInput, dp[i-3] + wines[i-2] + wines[i-1])
        dp.append(maxInput)
    }
}

print(dp[input])

 

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.