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

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

2156번: 포도주 시식

 

 

문제

효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다.

1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.

효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을 작성하시오. 

예를 들어 6개의 포도주 잔이 있고, 각각의 잔에 순서대로 6, 10, 13, 9, 8, 1 만큼의 포도주가 들어 있을 때, 첫 번째, 두 번째, 네 번째, 다섯 번째 포도주 잔을 선택하면 총 포도주 양이 33으로 최대로 마실 수 있다.

입력

첫째 줄에 포도주 잔의 개수 n이 주어진다. (1 ≤ n ≤ 10,000) 둘째 줄부터 n+1번째 줄까지 포도주 잔에 들어있는 포도주의 양이 순서대로 주어진다. 포도주의 양은 1,000 이하의 음이 아닌 정수이다.

출력

첫째 줄에 최대로 마실 수 있는 포도주의 양을 출력한다.

해결 방법

DP 점화식을 만들어서 푸는 것이 중요하다고 생각했다. 일단 다음과 같이 인덱스가 있다고 하자 A = {10 20 10 1 1 50 10 60 80} 우리는 생각할 때 다음과 같이 생각해야 한다. 순차적으로 DP값을 찾음에 있어서 전 DP값들을 생각해야 한다. 이것은 다시 말하면, DP값을 선택함에 있어서 값이 붙어있는 것인지 ex(10 20), 떨어져 있는 것인지 (10 20 10)을 명시적으로 생각할 필요가 있다. 이것을 그래서 DP값이 한개가 아닌 배열로 선언하여 그것을 확인한다. 

 

케이스는 3가지이다. 진행함에 있어서 arr[i]의dp[i]값을 구함에 있어서 arr[i - 1]이 사용되었는지 arr[i - 2]가 사용되었는지 arr[i - 2]가 사용되었는지 이 세가지이다. 3가지 케이스를 생각하여 문제를 해결하면 된다.

"앗 왜 i - 2까지 고려해야 하나요?"

반례로 A = {100, 100, 10, 10, 100, 100} 이 있다고 가정하자 그러면 가장 큰 값은 {100, 100, 10, 10, 100, 100} 이다. 따라서 우리는 현재 인덱스보다 3차례까지 생각할 필요가 있다. 그리고 dp값을 저장하는 배열 또한 연결되었는지 연결되지 않았는지 표현해야 한다.

핵심 1 . ind -2 와 ind -3 의 경우는 연결되었는지 중요하지 않다.

핵심 2. dp 배열을 ind-1과 ind가 연결되었을 때 값과 연결되지 않았을 때의 값으로 나눈다. 

Ex) dp = [[10, 0], [20, 30]] // dp[1]은 dp[1][0] = 20 (10과 연결하지 않음) dp[1][2] = 10 + 20으로 나눠서 생각한다. 

핵심 3. 최대 dp를 계산하는 방법은 마지막 인덱스와 마지막 인덱스 - 1 두개의 값 중에서 제일 큰 값을 고르면 된다.

 

예시

 

ind 가 0일때 선택할 수 있는 DP값은 {10}밖에 안된다. {10}은 dp[0][0]에 삽입된다.

	0	1	2	3	4	5	6	7	8
값	10	20	10	1	1	50	10	60	80
dp[0]	10
dp[1]

 

ind 가 1일 때 선택할 수 있는 DP값은 {10, 20} , {10 20} 중에 선택해야 한다. {10, 20}의 경우 붙어있다. 이것을 명시적으로 표현하기 위해서 dp[0] dp[1] 값을 나눈 것이다. 따라서 dp[1][0] = 30, dp[1][1] = [20]

 

	0	1	2	3	4	5	6	7	8
값	10	20	10	1	1	50	10	60	80
dp[0]	10	20
dp[1]		30 (10+20)

 

 

ind가 2일 경우는 DP값은 DP[ind - 2]의 값들중 가장 큰 값으로 계산하면 된다. DP[ind - 2]의 경우 Ind가 2인 10과 절대 붙지 않는다. 따라서 수도 코드로 표현하면 dp[2][0] = max(dp[0][0], dp[0][1]) + var[2]가 된다. 그리고 전 값과 붙는 경우를 가졍한다면

dp[2][1] = dp[i-1][0] + var[2]가 된다.

	0	1	2	3	4	5	6	7	8
값	10	20	10	1	1	50	10	60	80
dp[0]	10	20	20 (10 20 10)
dp[1]		30 (10+20)	30 (10 20 10)

 

 

ind가 3일 경우 한가지 가능성이 추가 된다. 바로 val[1]과 val[2]를 선택하지 않은 경우이다. 즉 A = { 10 20 10 1}를 의미한다. 

dp[3][0] = max(dp[0][0], dp[0][1], dp[1][0], dp[1][2]) + val[3]

dp[3][1] = dp[2][0] + var[3]

	0	1	2	3	4	5	6	7	8
값	10	20	10	1	1	50	10	60	80
dp[0]	10	20	20 (10 20 10)	31 (10 20 10 1)
dp[1]		30 (10+20)	30 (10 20 10)	21 (10 20 10 1)

 

 

ind가 4일 경우또한 마찬가지이다.

dp[4][0] = max(dp[1][0], dp[1][1], dp[2][0], dp[2][1]) + val[4] -> 값은 31이지만 (dp[1][1]과 dp[2][1]값이 같다.)

dp[4][1] = dp[3] + val[4]

	0	1	2	3	4	5	6	7	8
값	10	20	10	1	1	50	10	60	80
dp[0]	10	20	20 (10 20 10)	31 (10 20 10 1)	31
dp[1]		30 (10+20)	30 (10 20 10)	21 (10 20 10 1)	32

....

 

해서 표를 만들면 된다.

	0	1	2	3	4	5	6	7	8
값	10	20	10	1	1	50	10	60	80
dp[0]	10	20	20 (10 20 10)	31 (10 20 10 1)	31	81	42	141	171
dp[1]		30 (10+20)	30 (10 20 10)	21 (10 20 10 1)	32	81	91	102	221

 

그중 dp[8] 과 dp[7]의 값중 가잔 큰 값인 221이 정답이다.

func sol8() {
    let k = Int(readLine()!)!
    
    var inputArr = Array(repeating: 0, count: k)
    
    for i in 0 ..< k {
        let temp = Int(readLine()!)!
        inputArr[i] = temp
    }
    var dp =  Array(repeating: [0], count: k)
    
    if k <= 3 {
        inputArr.append(0)
        let tempVal = inputArr.sorted(by: >)
        print(tempVal[0] + tempVal[1])
    }
    else{
        dp[1] = [inputArr[1], inputArr[0] + inputArr[1]]
        dp[2] = [inputArr[2] + inputArr[0], inputArr[1] + inputArr[2]]
        dp[0] = [inputArr[0], 0]
        for i in 3 ..< k {
            let temp1 = max(dp[i - 2][0], dp[i - 2][1], dp[i - 3][0], dp[i - 3][1]) + inputArr[i]
            let temp2 = dp[i - 1][0] + inputArr[i]
            dp[i] = [temp1, temp2]
        }
        print(dp)
        let temp1 = dp.removeLast().max()!
        let temp2 = dp.removeLast().max()!
        print(max(temp1, temp2))
    }

}
sol8()

# 로직은 ind 가 3이상부터 시작하는 것으로 짜는 것이 훨 쉽다.

# 따라서 재량껏 k 가 1~3일 때의 DP의 값을 구하는 것으로 코드를 작성하였다.