버튼 누르기

1. 문제

2. 입출력

3. 입출력 예시

4. 문제 설계

• N이 100,000이기 때문에 O(N^2) 완전탐색으로 문제를 시간안에 해결할 수 없을 뿐더러, 이전에 선택했던 버튼을 다음 차례에서 선택하지 않고, 현재 차례에 선택한 버튼은 다음 차례에서 선택할 수 없고 이전 차례는 다음 차례에서 선택할 수 있는 패턴을 구현하기도 까다로움
• 따라서 현재 시점을 기준으로 이전 시점을 바라봤을 때, 현재 버튼을 선택하게 되면 이전 버튼에서 현재 버튼을 제외한 나머지 2버튼 중 최대 값을 현재 버튼 값에 더하는 패턴을 찾을 수 있고, 즉 이러한 과정을 N개의 시간에 대해 반복하게 되므로
• 작은 문제를 해결하여 큰 문제를 해결하는 동적 계획법을 사용할 수 있음
• 위 과정을 반복하고 최종적으로 N초에 해당 하는 값 중 최대값을 찾음으로써 문제를 해결하므로 O(N)의 시간복잡도로 해결할 수 있음

5. 전체 코드

//MARK: - 버튼 누르기

//MARK: - Framework
import Foundation

//MARK: - Function
func getMax(_ array: [[Int]], _ baseCondition: Int, _ N: Int) -> Int {
    var result: Int = 0
    
    for i in 0..<baseCondition {
        result = result < array[N - 1][i] ? array[N - 1][i] : result
    }
    
    return result
}

func solution() -> Void {
    //MARK: - Input
    guard let N: Int = Int(readLine() ?? "0") else { return }
    let baseCondition: Int = 3
    var result: Int = 0
    var buttonValues: [[Int]] = []
    
    for _ in 0..<N {
        guard let inputData: [String] = readLine()?.components(separatedBy: " ") else { return }
        buttonValues.append(inputData.map { Int($0) ?? 0 })
    }
    
    //MARK: - Process
    //1. 부분 문제를 정의한다.
    //max(T[N - 1][0], T[N - 1][1], T[N - 1][2) = 각 초마다 이전 시점에서 선택한 버튼을 제외한 버튼을 선택했을 때 누적합의 최대값
    
    //2. 점화식을 세운다.
    //T[i][0] += T[i - 1][1] < T[i - 1][2] ? T[i - 1][2] : T[i - 1][1]
    //T[i][1] += T[i - 1][0] < T[i - 1][2] ? T[i - 1][2] : T[i - 1][0]
    //T[i][2] += T[i - 1][0] < T[i - 1][1] ? T[i - 1][1] : T[i - 1][0]
    //...T[N - 1][0], T[N - 1][1], T[N - 1][2] 까지
    //max(T[N - 1][0], T[N - 1][1], T[N - 1][2)
    for i in stride(from: 1, to: N, by: 1) {
        buttonValues[i][0] += buttonValues[i - 1][1] < buttonValues[i - 1][2] ? buttonValues[i - 1][2] : buttonValues[i - 1][1]
        buttonValues[i][1] += buttonValues[i - 1][0] < buttonValues[i - 1][2] ? buttonValues[i - 1][2] : buttonValues[i - 1][0]
        buttonValues[i][2] += buttonValues[i - 1][1] < buttonValues[i - 1][0] ? buttonValues[i - 1][0] : buttonValues[i - 1][1]
    }
    
    result = getMax(buttonValues, baseCondition, N)
    
    //MARK: - Output
    print(result)
}
solution()

 

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