[Swift][DP] 백준 11060번 (점프 점프)

요구능력 : DP문제풀이

 

코드설명 : 

 

왼쪽끝을 1로두고 푸는사람들이 있는데 나는 왼쪽끝에서 시작이라서 안움직인게 맞다고보고 0으로 두고 풀었다.

문제를 잘보면 현재칸 + (1~점프숫자)까지 점프가 가능한것이다.

현재칸은 i로 잡아주고 1~점프숫자는 j로 for문을 생성했다.

 

가장중요한건 초기 dp숫자를 1001로 설정하는것이다.(Int.max도 가능)

문제에서 미로의 줄은 1~1000까지 주어진다고 했으니까

줄이 1000이 주어졌을때 한번씩 점프해도 1000까지 간다.

그러니까 최대 점프횟수는 1000인것이다.

초기 dp숫자를 1001로 설정해놓아야 n이 1000이 나와도 최소값으로 비교가 가능하고 dp[n]에 들어갈 수 있는 가장 큰 수는 1000인데 1001이라는 숫자가 그대로 들어가있다면 갈 수없는 경우이다.

나는 한번 dp[i] = i로 했다가 틀렸다.

 

i + j는 현재칸 + (1~점프숫자)를 구현한것이다.

 

후기 : 어찌저찌 거의다 풀었는데 조건이 안맞아서 헤맸다..

let n = Int(String(readLine()!))!
let arr = readLine()!.split(separator: " ").map{Int(String($0))!}
var dp = Array(repeating: 1001, count: 1001)
dp[1] = 0
for i in 1...n{
    for j in stride(from: 1, through: arr[i - 1], by: 1){
        if i + j <= n {
            dp[i + j] = min(dp[i] + 1, dp[i + j])
            }
        }
    }
if dp[n] == 1001 {
    print(-1)
}else{
    print(dp[n])
}