[Swift] 백준_포도주 시식(2156)

문제

 

https://www.acmicpc.net/problem/2156

2156번: 포도주 시식

 

 

풀이

 

보자마자 계단오르는 문제와 비슷하다고 생각해서 똑같이 풀었지만 바로 틀렸었다.

계단 문제는 1칸 또는 2칸을 반드시 올라가면서 끝까지 올라가야하는 문제였다. 연속해서 세 계단을 올라갈 수 없다는 조건과 연속으로 놓여있는 세 잔을 모두 마실 수 없다는 조건만 보고 같다고 판단하여 풀었던 것인데, 생각해보면 비슷하지만 다른 문제였다.

 

이 문제의 경우는 1잔 또는 2잔을 반드시 마셔야하는 것이 아니고, 3잔 이상 안마셔도 되는 것이다. 즉, 1잔 또는 2잔 이후에 반드시 마셔야 하는 것이 아니다. 그래서 계단 문제에서 추가적으로 마시지 않은 경우도 추가해주었다.

 

아무튼 풀이를 설명하자면, 

 

result[k][1]은 k번째까지 왔을 때 연속으로 1잔만 마시는 경우의 최대값을 의미한다. 즉, k번째 잔을 마시므로 k - 1번째 잔은 마시면 안되는 것이다. 그리고 k - 2번째까지는 1잔을 연속으로 마시던 2잔을 연속으로 마시던 상관이 없기 때문에 result[k - 2]의 max의 값에 현재 잔을 더해주었다.

 

result[k][2]는 k번째까지 왔을 때 연속으로 2잔만 마시는 경우를 의미한다. 즉, 반드시 k - 1번째 잔을 마신다는 얘기이고 k - 1번째와 k번째 잔을 마신다는 것은 k - 2번째 잔은 마시면 안된다는 얘기이다. 그렇기 때문에 result[k - 1][1]에 현재 잔을 더해준 값이 된다.

 

result[k][0]은 k번째 잔을 마시지 않은 경우이다. 이 부분이 계단 문제와 다른데, 계단 문제에서는 반드시 1칸이나 2칸 이후에 올라가야했기 때문에 현재 자신의 값을 계속해서 더해주어야 했다. 하지만 이 문제는 그러지 않아도 되고, 만약 계단 문제처럼 result[k][0]을 신경쓰지 않는다면, 이후의 값에 영향을 줄 수도 있다. k번째 잔을 마시지 않은 경우에는 바로 이전의 k - 1번째 잔 까지의 값 중 최대 값을 그대로 받으면 된다. 

import Foundation

let n = Int(readLine()!)!
var glass: [Int] = []
for _ in 0..<n {
    glass.append(Int(readLine()!)!)
}
var result = Array(repeating: Array(repeating: 0, count: 3), count: n + 1)
for i in 1...n {
    result[i][0] = max(result[i - 1][1], result[i - 1][2])
    result[i][1] = i == 1 ? glass[i - 1] : result[i - 2].max()! + glass[i - 1]
    result[i][2] = result[i - 1][1] + glass[i - 1]
}
print(result[n].max()!)

 

 

_____________________________________________________________________________________________________

 

 

이전보다 조금씩 감이 생기는 것 같지만 아직 시간이 오래걸린다.