[이.취.코] Chap 8. 다이나믹 프로그래밍 - 개미전사

1. 개미전사

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

A. 문제

개미 전사는 메뚜기 마을의 식량창고를 몰래 공격한다.
메뚜기 마을의 식량창고는 일직선으로 되어 있다.
각 식량창고에는 정해진 수의 식량을 저장하고 있으며 개미 전사는 식량창고를 선택적으로 약탈하여 식량을 빼앗을 예정이다.
메뚜기 정찰병은 일직선상에 존재하는 식량창고 중에서 서로 인접한 식량창고가 공격받으면 알아챌 수 있다. 따라서 개미 전사가 정찰병에게 들키지 않고 식량창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 한다.

개미 전사는 식량창고 N에 대한 정보가 주어졌을 때 얻을 수 있는 식량의 최댓값을 구하는 프로그램을 작성하라.

a. 예를 들면.

식량창고 4개가 아래와 같이 존재한다고 가정한다.


[1, 3, 1, 5]

이때 개미 전사는 두 번째 식량창고와 네 번째 식량 창고를 선택했을 때 최댓값인 8개의 식량을 빼앗을 수 있다.

b. 입력 조건
  • 첫째 줄에 식량창고의 개수 N이 주어진다
    • 3 <= N <= 100
  • 둘째 줄에 공백으로 구분되어 각 식량창고에 저장된 식량의 개수 K가 주어진다
    • 0 <= K <= 1000
c. 출력 조건
  • 첫째 줄에 개미 전사가 얻을 수 있는 식량의 최댓값을 출력하라.
d. 테스트 케이스
  • 입력 예시

    
    4
    1 3 1 5
    
    
  • 출력 예시

    
    8
    
    

B. 내 답안

a. 1차 풀이

n = int(input())  
array = list(map(int, input().split()))  
  
d = [0] * 101  
  
for i in range(2, n):  
    if i-3 < 0:  
        array[i] = array[i-2] + array[i]  
        continue  
  
    A = array[i-2] + array[i]  
    B = array[i-3] + array[i]  
  
    array[i] = max(A, B)  
  
print(array[-1])

b. 2차 풀이

n = int(input())  
array = list(map(int, input().split()))  
  
dp = [0] * 101  
dp[0] = array[0]  
dp[1] = array[1]  
  
for i in range(2, n):  
    dp[i] = max(dp[i-2] + array[i], dp[i-1])  
  
print(dp[n-1])

c. 회고

풀이

앞에서 푼 문제와 같이 그래프로 도식화하여 해결했다.

반성

다 잘했다고 생각했다. 그런데 문제 해설이랑 뭔가 다르다.

해설에서는 (자기 자신 + 누적값)과 (자기 자신 바로 앞 값)을 비교한다. 확실히 이 방식이 더 간단하고 직관적이다.

결론

최종 결과는 결국 맨 마지막과 그 앞 값을 비교하여 더 큰 것을 출력한다. 그래서 맨 마지막 값 + 맨 마지막 - 2번째 값 vs 맨 마지막 - 1번째 값을 비교하는게 맞다.

나는 f(x-2)이 f(x-3)보다 더 크다 해도 f(x)를 더하니까, 내가 푼 방식은 흐름은 맞지만, 결론은 틀렸다.

b. 점화식 추가 공부

점화식의 개념이 흐릿하다. 그냥 넘어가기에는 너무 찝찝하다. 그래서 유튜브로 개념을 다시 정리해보기로 했다. 모르는건 죄가 아니지만, 모르는 것을 무시하고 넘어가는 건 죄다. 나는 그렇게 생각한다.

점화식은 a_{1}, a_{2}를 알아야 이웃한 세 항 사이의 점화식을 알 수 있다. 즉, 적어도 2개의 항을 알아야함.

아래 영상을 보면 잊혀진 기억을 되살리는데 도움이 될듯함.

수열의 귀납적 정의 (1) - YouTube

C. 문제 해설

도식화해보면 아래와 같다. 식량을 선택할 수 있는 경우의 수는 8이다.

이 문제의 점화식은 아래 그림을 통해 유추할 수 있다.

  1. (i-1)번째 식량창고를 털기로 결정한 경우, 현재의 식량창고를 털 수 없다.
  2. (i-2)번째 식량창고를 털기로 결정한 경우 현재의 식량창고를 털 수 있다.

점화식

a. 책 답안

python-for-coding-test/6.py at master · ndb796/python-for-coding-test (github.com)

참고문헌

나동빈, "이것이 취업을 위한 코딩 테스트다 with 파이썬", 초판, 2쇄, 한빛미디어, 2020년

#코딩테스트 #파이썬 #나동빈 #한빛미디어 #문제 #풀이 #다이나믹프로그래밍 #개미전사

이 글이 도움이 되었나요?

신고하기
0분 전
작성된 댓글이 없습니다. 첫 댓글을 달아보세요!
    댓글을 작성하려면 로그인이 필요합니다.