1. 문제 설명
메뚜기 마을에는 여러 식량창고가 있는데, 일직선으로 이어져 있다. 각 식량창고에는 정해진 수의 식량이 있고, 개미는 선택적으로 창고를 약탈할 계획이다. 메뚜기 정찰병은 개미가 특정 식량창고를 털고, 인접한 식량창고에 접근하여 약탈 할 때 이를 알아차린다.
이 때, 개미가 정찰병한테 들키지 않고 약탈하기 위해선 최소한 한 칸 떨어진 창고를 약탈해야 한다. 예를 들어 다음과 같은 식량창고가 있다.
{ 1, 3, 1, 5 }
그럼 개미는 2째, 4째 식량창고를 털어 최대 8의 식량을 얻는다. 이 경우처럼 식량 창고가 주어질 때 식량 최댓값을 구해보시오.
입력 조건은 다음과 같다.
- 식량 창고 개수 N ( 3 ≤ N ≤ 100 )
- 각 식량창고에 식량 개수 K ( 0 ≤ K ≤ 1000 )
2. 문제 해결
언뜻봐선, DP 유형의 문제라고 생각되지 않는다. 하지만 점화식을 구할 수 있다.
왼쪽부터 식량창고를 턴다고 가정해보자. ( 식량창고 리스트에서, 0번째 인덱스부터 시작한다고 가정 )
그래서 왼쪽부터 식량창고를 털지 안 털지 결정할 경우 + 특정 i 번쨰 인덱스 식량창고를 털지 안 털지 결정할 경우 조건을 통해 생각해보면 다음과 같다. ( i는 현재의 위치라고 가정, 빨간색은 턴다고 마크한 경우 )
[0], [1], ~ [i-2], [i-1], [i] <= 현재 위치를 털 수 없는 경우
[0], [1], ~ [i-2], [i-1], [i] <= 현재 위치를 털 경우
알아야 할 건, 이미 왼쪽 위치( 현재 인덱스 이전 )의 식량창고는 모두 털었다고 생각하자 ( 현재 위치 이전에 대해선 최대의 식량을 얻음 )
왜냐면, i - 3 번째 이하 식량창고는 항상 털 수 있기 때문이다.
이 두 경우에 대해 더 많은 식량을 털 수 있는 경우를 선택하면 된다.
이미 왼쪽 위치의 식량창고를 털었다는 건, 이전의 결과값을 얻고 이를 이용한다는 의미와 같다. 즉, DP로 풀기 가장 적합한 문제라는 의미이다.
i번째 식량 창고에 식량이 ki 라고 할 때, 다음과 같이 점화식이 구해진다.
a[i] = max(a[i-1], a[i-2] + ki )
이를 코드로 구현하면 다음과 같다.
3. 느낀 점
역시 아이디어를 얻기가 너무 어려웠다. 분명한 건 규칙을 찾고, 이를 점화식으로 구현할 수 있냐가 관건이다. 그래서 그리디로 접근하여 규칙을 찾되, 점화식을 구할 수 있고 기타 DP 조건을 만족하면 DP로 해결하도록 하자.