[다이나믹프로그래밍] 개미전사 / Swift

[문제 보기]

개미 전사 문제 (교재 220p)

난이도 ●●○ | 풀이 시간 30분 | 시간 제한 1초 | 메모리 제한 128MB

 

개미 전사는 부족한 식량을 충당하고자 메뚜기 마을의 식량창고를 몰래 공격하려고 한다. 메뚜기 마을의 식량창고는 일직선으로 이어져있다. 개미 전사가 정찰병에게 들키지 않고 식량창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 한다. 개미 전사는 최대한 많은 식량을 얻기를 원한다. 개미 전사를 위해 식량창고 N개에 대한 정보가 주어졌을 때 얻을 수 있는 식량의 최댓값을 구하는 프로그램을 작성하시오.

 

입출력 조건)

입력 조건	- 첫째 줄에 식량창고의 개수 N이 주어진다. (3 ≤ N ≤ 100)  - 둘째 줄에 공백으로 구분되어 각 식량창고에 저장된 식량의 개수 K가 주어진다. (0 ≤ N ≤ 1,000)
출력 조건	첫째 줄에 개미 전사가 얻을 수 있는 식량의 최댓값을 출력하시오.

입출력 예시)

입력 예시	출력 예시
4 1 3 1 5	8

 

---

 

dp 문제는 점화식을 어떻게 세울지 잘 생각해야한다.

문제에서 요구하는 정답 f(n)을 구하기위해 작은 부분 문제로 쪼갤건지 (top-down) 아니면 처음부터 차근차근 구해서 f(n)을 구할건지 (bottom-up) 이 둘중 어떤 방식으로 구할건지 생각하는 것부터 시작한다.

 

잘 관찰하면 길이 n개의 상황일 때의 최대값은 (n-2번째까지의 최대값 + n번째원소값)과 (n-1번째까지의 최대값) 이 둘중 큰 값이 되는 것을 확인할 수 있다.

 

관찰을 통해 세운 점화식 

 

 

여기서 처음 1번째와 2번째는 예외 사항으로 dp배열에 따로 직접 수동으로 값을 채워준다.

그래서 값을 계산하기 시작하는 첫 값은 3번째부터 시작하게 된다.

반복문에 처음 들어갔을 때의 상황 (3번째부터 시작하게 됨)

 

위 점화식을 토대로 구현한 코드는 아래와 같다.

func solution(_ n : Int, _ arr: [Int]) -> Int {
    var dp = [Int](repeating: 0, count: n + 1)
    dp[1] = arr[0]
    dp[2] = max(arr[0], arr[1])
    if n < 2 {
        return dp[2]
    }
    for i in stride(from: 3, through: n, by: 1) {
        dp[i] = max(dp[i - 1], arr[i - 1] + dp[i - 2])
    }
    
    return dp[n]
}