[TIL] 다이나믹 프로그래밍 (동적 계획법, DP) / 이코테 - 금광, 병사 배치하기

[Today I Learned]

어제에 이어서 다이나믹 프로그래밍을 계속 공부했다.

# 이코테 - 금광

문제
n x m 크기의 금광이 있습니다. 금광은 1 x 1 크기의 칸으로 나누어져 있으며, 각 칸은 특정한 크기의 금이 들어 있습니다. 채굴자는 첫 번째 열부터 출발하여 금을 캐기 시작합니다. 맨 처음에는 첫 번째 열의 어느 행에서든 출발할 수 있습니다. 이후에 m - 1번에 걸쳐서 매번 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의 위치로 이동해야 합니다. 결과적으로 채굴자가 얻을 수 있는 금의 최대 크기를 출력하는 프로그램을 작성하세요.

 

@solution.py

생각의 흐름은 다음과 같았다.

1. 각 칸에서 최선의 선택을 한다고 그것이 항상 최선의 결과를 가져오지는 않음 ( != 그리디 알고리즘) 따라서 모든 경로를 고려하긴 해야 함.

2. 그렇다면 어떻게 연산을 줄일 수 있을까?  임의의 칸에서 그 이후로 얻을 수 있는 최대 채굴량은 모두 동일. 따라서 반복 연산할 필요가 없다.
→ 임의의 칸에 도달할 때까지 최대 채굴량을 계산해나가자.
→ 앞 열에서 다음 열로 나아가는 식으로 계산하는 것보다 다음 열에서 이전 열을 확인하면서 최선의 값을 저장하는 방식이 효율적일 것일 것 같다. 

 (생각한 걸 말로 쓰는 게 어렵네 ㅠ_ㅠ)

import numpy as np

T = int(input()) # 테스트 케이스 개수

for t in range(T):

    n, m = map(int, input().split()) # n x m
    golds = list(map(int, input().split()))
    golds = (np.array(golds).reshape(n,m)).tolist()

    for j in range(1,m):
        for i in range(n):

            lu, ll, ld = -1, -1, -1

            # 왼쪽 위
            if i-1 >= 0 and j-1 >= 0:
                lu = golds[i][j] + golds[i-1][j-1]

            # 왼쪽
            if j-1 >= 0:
                ll = golds[i][j] + golds[i][j-1]

            # 왼쪽 아래
            if i+1 < n and j-1 >= 0:
                ld = golds[i][j] + golds[i+1][j-1]

            golds[i][j] = max(lu, ll, ld)

    print(max(np.array(golds).T[-1]))

list보다는 array를 다루는 게 더 편하다 보니 numpy도 사용했다.

그리고 강의에서는 다음과 같이 풀이했다.

for tc in range(int(input())) :
  n, m = map(int, input().split())
  arr = list(map(int, input().split()))
  dp = []
  index = 0
  for i in range(n) :
    dp.append(arr[index: index + m])
    index += m

  for j in range(1, m) :
    for i in range(n) :
      if i == 0:
        left_up = 0
      else :
        left_up = dp[i - 1][j - 1]

      if i == n - 1 :
        left_down = 0
      else :
        left_down = dp[i + 1][j - 1]

      left = dp[i][j - 1]
      dp[i][j] = dp[i][j] + max(left_up, left_down, left)

  result = 0
  for i in range(n) :
    result = max(result, dp[i][m - 1])
  print(result)

내가 더 잘 푼 것 같기도,,ㅎㅎ
내 코드에서 정리할 부분이 있다면 j-1은 항상 충족하는 기준이므로 빼줘도 될 것 같다. 

 

# 이코테 - 병사 배치하기

문제

N명의 병사가 무작위로 나열되어 있다. 각 병사는 특정한 값의 전투력을 보유하고 있으며, 병사를 배치할 때는 전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치를 하고자 한다. 다시 말해 앞쪽에 있는 병사의 전투력이 항상 뒤쪽에 있는 병사보다 높아야 한다.
또한 배치 과정에서는 특정한 위치에 있는 병사를 열외시키는 방법을 이용한다. 그러면서도 남아있는 병사의 수가 최대가 되도록 하고 싶다.

+ 백준에도 있는 문제다. (https://www.acmicpc.net/problem/18353)

 

@solution.py

어떻게 풀어야 할지 감이 잘 안 와서, 유사한 문제인 LIS 계산 알고리즘을 우선 참고했다. 

'마지막 원소로 가지는 부분 수열의 최대 길이'

이 알고리즘을 코드로 구현하면 다음과 같다.

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

dp = [1] * n

for i in range(1, n):
	for j in range(0, i):
		if array[j] < array[i]:
			dp[i] = max(dp[i], dp[j] + 1)

 

이해를 위해,  i = 3일 때를 생각해보자.

j = 0 ) array[j = 0] = 4 < array[3] = 8 이기 때문에 조건문 동작. dp[3] = max(dp[3], dp[0] + 1) = max(1,2) = 2
j = 1 ) array[j = 1] = 2 < array[3] = 8 이기 때문에 조건문 동작. dp[3] = max(dp[3], dp[1] + 1) = max(2,2) = 2
j = 2 ) array[j = 2] = 5 < array[3] = 8 이기 때문에 조건문 동작. dp[3] = max(dp[3], dp[2] + 1) = max(2,3) = 3

이해하기 어렵다... 

강의에서는 문제에 입력된 array를 reverse해서 LIS 알고리즘을 적용하는 식으로 풀이했는데, 나는 내가 제대로 이해했는지 확인해보고 싶어서... 처음부터 알고리즘을 새로 짰다.

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

dp = [1] * n

for i in range(1,n):
    for j in range(0,i): # idx
        if sols[i] < sols[j]:
            dp[i] = max(dp[i], dp[j]+1)

print(n - max(dp))

백준 제출 5번만에 정답..!
그림 그리면서 어떤 수열을 계산해서 dp 값을 채운 건지 따져본 게 이해에 많은 도움이 됐다.