다이나믹 프로그래밍 - 개미 전사(Swift)

본 내용은 '이것이 취업을 위한 코딩테스트다 with 파이썬' 책을 기반으로 포스팅 하였습니다.

 

문제

저작권 문제가 될 수 있어 문제는 삭제합니다.

 

풀이 코드

let n = 4
let k = [1,3,1,5]

var dp = Array(repeating: 0, count: 100)

// dp[0] 위치에 1 추가
dp[0] = k[0]

// dp[1] 위치에 입력받은 k배열의 0,1위치값중 큰 값 추가
dp[1] = max(k[0],k[1])

for i in 2..<n {
    dp[i] = max(dp[i-1], dp[i-2] + k[i])
}

print(dp[n-1]) // 8

/*
 최적의 해를 구해보면
 창고 => k = |1|3|1|5|
 
 창고가 1개일때 -> 1
 창고가 2개일때 -> 3
 창고가 3개일때 -> 3
 창고가 4개일때 -> 8
 
 최소한 한칸 이상 떨어진 식량창고를 약탈해야하기 때문에 점화식을 구해보면
 현재위치의 -1의 위치의 값, 현재위치의 -2의 위치의 값 + 현재위치 값으로 2가지 경우를 가지고 비교해볼수 있다.
 # dp[i-1], (dp[i-2] + k[i])
 
 k = |1|3|1|5|
 위 배열에서 2가지 경우를 계산 하려면 2번째 위치에서부터 시작해야하며
 
 i = 2
 |0|1|2|3|
 |1|3|1|5|
 dp[i-1] => 3
 dp[i-2] + k[i] => 1 + 1 = 2
 둘중 큰 식량 개수 3
 dp[i] = 3
 
 i = 3
 |0|1|2|3|
 |1|3|1|5|
 dp[i-1] => 1
 dp[i-2] + k[i] => 3 + 5 = 8
 둘중 큰 식량 개수 8
 dp[i] = 8
 */

 

문제 풀이

주석 참고