silver1-12026.md

Baekjoon

BOJ 거리

• 분류: 다이나믹 프로그래밍
• 풀이 언어: Swift
• 문제 요약: 특정한 순서로 보도블럭을 밟아야 하고 k*k의 에너지로 k칸 만큼 점프할 수 있을 때, 1번에서 N번에 도착하는 데 필요한 에너지 양의 최솟값 구하기

코드

let n = Int(readLine()!)!
let blocks = readLine()!.map { String($0) }
var d = [Int](repeating: Int.max, count: n)
d[0] = 0

for i in 0..<n {
    if d[i] == Int.max { continue }
    var next = ""
    if blocks[i] == "B" {
        next = "O"
    } else if blocks[i] == "O" {
        next = "J"
    } else {
        next = "B"
    }
    
    for j in i + 1..<n {
        if blocks[j] == next {
            d[j] = min(d[j], (j - i) * (j - i) + d[i])
            print(d)
        }
    }
}

print(d[n - 1] == Int.max ? -1 : d[n - 1])

• 메모리: 62228 KB
• 시간: 16 ms

회고

• 음 아직도 어렵게만 느껴지는 DP 문제. 이 문제도 다른 풀이를 많이 참고해 풀었다. 일단은 이전에 계산했던 값을 저장해두었다가 필요할 때 재활용하는 요 포인트를 잘 기억해두어야겠다.