[백준 12026] BOJ 거리 (Swift)

https://www.acmicpc.net/problem/12026

 

DP

B,O,J 중 하나가 쓰여있는 한줄짜리 보도블록들을 걸을 때 B->O->J 순으로 갈 수 있다고 할 때,

k칸 이동할 때 k*k의 에너지가 든다고 한다. 최소 에너지만을 사용해서 1번째에서 N번째 까지 도달하는 데 소모되는 최소 에너지를 출력하는 문제, 도달할 수 없다면 -1 출력.

 

접근방법

N의 범위가 1000까지여서 첫번째 칸부터 시작해서, 한번에 갈 수 있는 칸까지 가는데 필요한 에너지를 구하고, 그 칸에 도달하는 최소 에너지를 갱신해가면서 풀어도 N*N보다 적게 나온다. (1000*1000 = 1,000,000 이니까 근데 이것보다 확실히 적게 드니까 괜찮지 않을까 싶어서 그렇게 풀었다. 도달할 수 있는 칸을 배열에 넣고 그 칸들만 간다고 해도 중복해서 방문하는 칸이 있을 것 같아서 흠 그냥 가장 단순한 방법으로 풀었는데 통과!)

 

전체 칸을 한번씩은 본다. 보면서 도달 가능한 칸인 경우,

(dp 배열에 최소 에너지 값을 저장했다. -1로 초기화 해두고 -1이면 도달 불가능 한 칸, 0이상이면 도달 가능한 칸)

그 칸에서부터 갈 수 있는 다음 칸들에 대해, 최소 에너지 값을 갱신해준다.

(갈 수 있는 다음 칸의 조건 현재칸의 다음 순서 알파벳이어야 함 -> 딕셔너리를 썼다. B -> O, O->J, J->B)

 

반복문에 들어가기 전에 0번째 칸(스타트 집)의 dp값을 0으로 초기화해주면 0번째 부터 시작하게 된다.

 

소스코드

import Foundation

func solution() -> Int {
    let N:Int = Int(readLine()!)!
    let road:[Character] = Array(readLine()!)
    let next:[Character:Character] = ["B":"O", "O":"J", "J":"B"]
    
    var dp:[Int] = [Int](repeating: -1, count: N)
    dp[0] = 0
    for i in 0..<N {
        if dp[i] >= 0 {
            // i번째 보도블럭이 도달가능한 곳이면 -> 다음 도달 가능한 곳 찾기
            for j in i+1..<N {
                if road[j] == next[road[i]] {
                    if dp[j] == -1 {
                        dp[j] = dp[i]+(j-i)*(j-i)
                    } else {
                        dp[j] = min(dp[i]+(j-i)*(j-i), dp[j])
                    }
                }
            }
        }
    }
    
    return dp[N-1]
}

print(solution())