[Python/코테] 다이나믹 프로그래밍(2) - 예제: 개미 전사, 1로 만들기

개념 설명은 아래 포스팅 참고

2023.07.14 - [Coding Test] - [Python/코테] 다이나믹 프로그래밍(1) - 개념, 피보나치 수열 구현, 메모이제이션

[Python/코테] 다이나믹 프로그래밍 - 개념, 피보나치 수열 구현, 메모이제이션

---

1. 개미 전사

식량창고 N개에 대한 정보가 배열로 {1, 2, 4, 3} 주어졌을 때 얻을 수 있는 식량의 최댓값을 구하는 프로그램을 작성하라.

 

* Solution: 배열의 길이가 무수히 늘어날 수 있으므로 $a_i=i번째 식량창고까지의 최적의 해$ 로 정의하여 DP를 적용할 수 있다.

최적 부분 구조, 중복 문제 조건이 성립하므로 DP 알고리즘을 활용할 수 있다.

위의 왼쪽 사진에서 i-1번째까지의 합, i-2번째까지+현재 값의 합 두 개로 나누어 고려해본다. 두 가지 경우 중 큰 값에 i번째 원소(현재값)를 더하는 것이 최대합이 될테니.

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

d = [0] * 100	# 문제에서 주어진 범위

# 다이나믹 프로그래밍 진행 (보텀업)
d[0] = array[0]
d[1] = max(array[0], array[1])

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

print(d[n-1])

* 나다어

• 무수히 많은 경우의 수를 가진 경우, 주어진 문제 상황을 쪼개어 생각해보자. 🙅🏻한번에 모든 경우의 수를 커버하려고 하지 말기🙅🏻
  ex) i번째 위치의 창고를 털 수 있는가 없는가?
• 조건 또한 단순하게 적용해보자.
  ex) 3개가 인접해 있을 때 경우의 수만. 4개면.. 5개면.. 경우의 수가 달라지고 많아지겠지만 일반적인 경우를 정의하여 확장하자 → 즉 점화식을 정의하는 것과 같다.

2. 1로 만들기

* Solution: 최적 부분 구조(각 값을 구하기 위해 더 작은 값의 문제가 사용된다.)와 중복되는 부분 문제를 만족한다.

1을 더하는 이유는 함수의 호출 횟수를 구해야 하기 때문에, 1번의 연산을 수행했다는 의미.

x = int(input())

d = [0] * 30001

for i in range(2, x+1):
    # case1. 현재 수에서 1을 빼는 경우
    d[i] = d[i-1] + 1
    # case2. 현재 수가 2로 나누어 떨어지는 경우
    if i % 2 == 0:
        d[i] = min(d[i], d[i//2]+1)
    # case3. 현재 수가 3으로 나누어 떨어지는 경우
    if i % 3 == 0:
        d[i] = min(d[i], d[i//3]+1)
    # case4. 현재 수가 5로 나누어 떨어지는 경우
    if i % 5 == 0:
        d[i] = min(d[i], d[i//5]+1)
    
print(d[x])