자원 채취

1. 문제

2. 입출력

3. 입출력 예시

4. 문제 설계

• 로봇의 시작점에서 오른쪽과 아래쪽으로만 이동할 수 있는 것을 반대로 생각하면, 종착점을 기준으로는
• 왼쪽과 위쪽에서 더 큰 자원을 수집하면서 종착점까지 도달할 것임을 예측할 수 있음
• 따라서 큰 문제를 해결하기 위해 작은 문제부터 차근차근 해결해 나가는 동적 계획법으로 문제를 해결할 수 있음
• 따라서, T[i][j] = 나를 기준으로 왼쪽과 오른쪽 중 더 큰 값을 나에게 더한 값이고,
• T[i][j] + Max(T[i - 1][j], T[i][j - 1])로 점화식을 세울 수 있음
• (0, 0)에서는 위와 왼쪽이 없으므로, (1, 1)부터 원소를 채워놓고 위 점화식을 적용하여 최종적으로 T[N][M]에 누적된 값이
• 정답이며, O(N * M)의 시간복잡도로 문제를 해결할 수 있음

5. 전체 코드

//MARK: - 자원 채취

//MARK: - Framework
import Foundation

//MARK: - Function
func solution() -> Void {
    //MARK: - Input
    guard let input = readLine()?.components(separatedBy: " ") else { return }
    let N: Int = input.map { Int($0) }[0] ?? 0
    let M: Int = input.map { Int($0) }[1] ?? 0
    var table: [[Int]] = Array(repeating: Array(repeating: 0, count: M + 10), count: N + 10)
    
    for i in 1...N {
        guard let inputArray = readLine()?.components(separatedBy: " ") else { return }
        
        for j in 1...M {
            table[i][j] = inputArray.map { Int($0) ?? 0 }[j - 1]
        }
    }
    
    //MARK: - Process
    for i in 1...N {
        for j in 1...M {
            table[i][j] += table[i][j - 1] < table[i - 1][j] ? table[i - 1][j] : table[i][j - 1]
        }
    }
    
    //MARK: - Output
    print(table[N][M])
}
solution()

 

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