카드 놀이

1. 문제

2. 입출력

3. 입출력 예시

4. 문제 설계

• 연속하여 3개의 카드를 가져갈 수 없으므로, 카드를 가져가는 경우는 3가지로 나뉨
• 1. 현재 카드를 가져가지 않는 경우
• 2. 현재 카드를 가져가고 이전 카드를 가져가지 않는 경우
• 3. 현재 카드를 가져가고 이전 카드도 가져가는 경우
• 위 3가지 경우에 대한 최대값을 각각 저장해놓고 최종적으로 3가지 경우 중 최대값을 찾음으로써 문제를 해결할 수 있으며, 동적 계획법을 사용한 알고리즘
• 현재 카드를 가져가지 않는 경우에는 이전 카드에 대한 위 3가지 경우 중 최대값을 저장해야함
• 현재 카드를 가져가고 이전 카드를 가져가지 않는 경우는 현재 카드의 값에 이전 카드를 가져가지 않았을 때의 값을 저장
• 현재 카드와 이전 카드를 모두 가져가는 경우는 현재 카드의 값에 이전 카드만 가져갔을 때의 값을 저장
• 위 과정을 N개의 카드에 대해 반복한 후 3가지 경우에 대해 최대값을 구함으로써 문제를 해결함

5. 전체 코드

//MARK: - 카드 놀이

//MARK: - Framework
import Foundation

//MARK: - Function
func getMax(_ array: [Int]) -> Int {
    var result: Int = 0
    for number in array {
        result = result < number ? number : result
    }
    
    return result
}

func solution() -> Void {
    //MARK: - Input
    guard let N: Int = Int(readLine() ?? "0") else { return }
    guard let inputArray: [String] = readLine()?.components(separatedBy: " ") else { return }
    
    let baseCondition: Int = 3
    var result: Int = 0
    let cards: [Int] = inputArray.map { Int($0) ?? 0 }
    var cases: [Int] = Array(repeating: 0, count: baseCondition)
    
    //MARK: - Process
    //1. 부분 문제를 정의한다.
    //max(T[0], T[1], T[2]) = 주어진 카드에서 연속해서 최대 2장씩 뽑았을 때, 최대값
    
    //2. 점화식을 세운다.
    //T[0] = i번째 카드를 뽑지 않은 경우, 이전 경우에서 최대값
    //T[1] = i번째 카드만 뽑은 경우
    //T[2] = i번째 카드 + i - 1번째 카드 두장을 뽑은 경우
    //max(T[0], T[1], T[2])
    cases[0] = 0
    cases[1] = cards[0]
    cases[2] = cases[0] + cards[0]
    
    for i in 1..<N {
        let choiceNoting, choiceOne, choiceTwo: Int
        choiceNoting = getMax(cases)
        choiceOne = cards[i] + cases[0]
        choiceTwo = cards[i] + cases[1]
        
        
        cases[0] = choiceNoting
        cases[1] = choiceOne
        cases[2] = choiceTwo
    }
    
    result = getMax(cases)
    
    //MARK: - Output
    print(result)
}
solution()

 

전체코드는 여기에서 확인할 수 있습니다.