개미전사 - DP (근데 이제 롯데정보통신 코테 후기를 곁들인)

이것이 코딩테스트다 8장 다이나믹 프로그래밍에 실전문제로 나와있는 개미전사를 풀어보겠습니다. 

살짝 tmi이지만 지난주 주말 롯데정보통신에 코딩테스트가 있었는데요.

롯데정보통신은 코딩테스트 3문제와 SQL 1문제가 나옵니다.

코딩테스트 3문제 중에서 마지막 3번째 문제로 DP문제가 나왔습니다.

이게 제일 어려웠던 문제였습니다.(저만 어려웠을 수도..?) 

 

그리고 알고리즘 오픈카톡방에서 어떤 분이 해설해주시는 것을 봤습니다. 

근데 저는 이 문제가 떠오르더라고요. 물론 완전히 똑같은 것도 아니고, 코딩테스트 문제는 더 어려웠습니다.

후에 DP를 더 공부해서 보는 눈을 기른 후에,

백준이나 다른 코테 준비 사이트에서 비슷한 문제를 발견한다면 나중에 이 글에 정보를 남기겠습니다.

 

개미전사 문제를 풀어보면서 제가 비슷했다고 생각했던 포인트를 말씀드리겠습니다.

 

문제요약) 개미전사는 식량창고를 선택적으로 약탈하여 식량을 빼앗을 예정입니다.

일직선상으로 존재하는 식량창고는 인접한 식량창고가 공격받으면 바로 알아차리기 때문에

최소한 한 칸 이상 떨어진 식량 창고를 약탈해야 합니다. 식량의 최댓값을 구하세요.

1

3

1

5

위의 표는 일직선상으로 존재하는 식량창고와 각 식량창고에 저장된 식량의 개수를 나타냅니다.

 

DP문제를 푸는 순서는 대략 이런식인 것 같습니다.

1. 이것이 DP문제임을 알아 챈다.

2. 점화식을 구한다. d[i]정의하기 

3. 초기값을 구한다. 

 

1번은 책에도 나와있듯이

완전탐색으로 접근했을 때 시간이 오래걸린다면 DP를 떠올리셔야 합니다. 

 

2번은 규칙을 찾는 과정인데 이 부분이 제일 어렵죠;;

이제 여기서 제가 롯데정보통신 코딩테스트 문제와 이 문제가 비슷하다고 생각했던 부분이 나오는데요.

바로 '마지막으로 어떤 행동을 했느냐를 기준으로 묶는다.'는 개념입니다. 

이 문제는 마지막 창고를 턴다 와 안턴다.

단 2가지 경우에 대해서만 생각하면 되는 문제인데요.

d[i]는 i+1번째 식량창고까지의 얻을 수 있는 최대 식량입니다. 

따라서 점화식은 d[i] = max(d[i-1], d[i-2]+마지막 칸의 식량) 입니다.

 

롯데정보통신 DP문제는 마지막이 어떤 숫자로 끝나냐로 점화식을 세웠습니다.

(물론 다른 분의 풀이에서요...!)

 

마지막 3번 초기값은 개미전사 문제에서는

d[0]은 1번째 식량창고까지의 얻을 수 있는 최대 식량이므로, 1번째 식량값이고, 

d[1]은 2번째 식량창고까지의 얻을 수 있는 최대 식량이므로 max(1번째 식량값, 2번째 식량값)입니다.

 

이상으로 개미전사를 풀어보면서 DP문제를 푸는 방법론에 대한 얘기를 살짝쿵 해봤는데요.

저의 작은 경험을 빗대어보면 이런방식의 DP문제가 꽤 많습니다. 

물론 이 사실을 알고 있더라고 푸는 건 또 다른 문제이지 만요..ㅠ

 

그래도 DP를 완전 처음 접하시는 분들에게 도움이 되셨기를 바라면서

개미전사 정답코드를 마지막으로 글을 마무리하겠습니다.

화이팅!!

 

 

정답코드)

n = int(input())
arr = list(map(int,input().split()))

d = [0] * 100

d[0] = arr[0]
d[1] = max(arr[0],arr[1])
for i in range(2,n):
	d[i] = max(d[i-1],d[i-2]+arr[i])
    
print(d[n-1])