반응형
문제
개미 전사는 부족한 식량을 충당하고자 메뚜기 마을의 식량창고를 침입합니다. 식량창고는 정해진 수의 식량을 저장하고 있고 일직선으로 나열되어 있습니다. 메뚜기 정찰병은 인접한 식량창고가 공격받으면 바로 알아차릴 수 있습니다. 따라서, 개미 전사가 정찰병에게 들키지 않고 식량창고를 털기 위해서는 최소한 한 칸 이상 떨어진 식량창고를 공격해야 합니다. 식량창고가 배열로 주어졌을 때, 개미 전사가 약탈할 수 있는 최대 식량을 구하는 문제입니다.
1. [1,3,1,5] => 8
2. [1,2,3,1] => 4
3. [2,7,9,3,1] => 12
풀이
1번 케이스의 [1,3,1,5]를 생각해보면, 개미가 첫 번째 인덱스를 (1) 약탈한다면 세 번째 인덱스 (1) 이나 네 번째 인덱스밖에 (5) 약탈할 수 없습니다. 이 경우 식량의 합은 6이 되겠네요. 두 번째 인덱스부터 (3) 약탈한다면 네 번째 인덱스밖에 (5) 약탈할 수 없으므로 식량의 합은 8이 됩니다. 따라서 8이 정답입니다.
배열 $a$의 원소가 $n$개 있다고 가정해 봅시다. 이 때 약탈할 수 있는 최대값은 어떻게 구할 수 있을까요? 최소한 한 칸 이상 떨어져야 되니 $n-1$에서의 식량 최대값과 $n-2$의 식량 최대값에서 $a_{n}$을 더한 값의 최대값이 되겠죠. 여기서 생각나는 부분은 바로 다이나믹 프로그래밍입니다.
- 최적 부분 구조를 만족합니다. $n$에서의 식량 최대값을 하위 문제인 $n-1, n-2$에서의 식량 최대값을 통해 구할 수 있기 때문입니다.
- 위의 하위 문제들은 중복됩니다.
kaggle.com의 notebook으로 작성한 풀이는 다음과 같습니다.
다이나믹 프로그래밍의 상향식 테뷸레이션으로 풀이했습니다.
홍머스 정리
- 다이나믹 프로그래밍, tabulation
- 난이도: 중, 바로 다이나믹 프로그래밍을 생각하기 쉽지 않다.
참조
반응형
'Computer > Coding Test' 카테고리의 다른 글
| 코딩테스트 문제 (10) - 배열의 K 번째 큰 요소 (0) | 2021.02.24 |
|---|---|
| 코딩테스트 문제 (9) - 효율적인 화폐구성 (0) | 2021.02.24 |
| 코딩테스트 문제 (7) - 계단 오르기 (0) | 2021.02.24 |
| 코딩테스트 문제 (6) - 연속적으로 반복되는 최대 문자열 길이 (0) | 2021.02.23 |
| 코딩테스트 문제 (5) - 가장 큰 수 (0) | 2021.02.23 |
