[BOJ, Swift] 1932 - 정수 삼각형

1932번: 정수 삼각형

1. 재귀 ( 시간 초과 )

let cheung = Int(readLine()!)!
var pyramid: [[Int]] = []
var result: Set<Int> = []
for _ in 0 ... cheung - 1 {
    pyramid.append(readLine()!.split(separator: " ").map { Int(String($0))! })
}

func SOT(_ floor: Int, _ x: Int, sum: Int) {
    if floor == cheung {
        result.insert(sum)
        return
    } else {
        SOT(floor + 1, x, sum: sum + pyramid[floor][x])
        SOT(floor + 1, x + 1, sum: sum + pyramid[floor][x])
    }
}

SOT(0, 0, sum: 0)
print(Int(result.max()!))

2.  메모이제이션 ( AC )

let cheung = Int(readLine()!)!
var pyramid: [[Int]] = []
for _ in 0 ... cheung - 1 {
    pyramid.append(readLine()!.split(separator: " ").map { Int(String($0))! })
}


if cheung == 1 {
    print(pyramid[0][0])
} else {
    for i in 1 ... pyramid.count - 1 {
        for j in 0 ... pyramid[i].count - 1 {
            if j == 0 {
                pyramid[i][j] += pyramid[i-1][j]
            } else if j == pyramid[i].count - 1 {
                pyramid[i][j] += pyramid[i-1][j-1]
            } else {
                pyramid[i][j] += [pyramid[i-1][j], pyramid[i-1][j-1]].max()!
            }
        }
    }
    print(pyramid[pyramid.count-1].max()!)
}