[다이나믹 프로그래밍] ★ 문제6 - 병사 배치하기(59:50)

[이코테] 문제6 - 병사 배치하기(59:50)

(한줄평) 아이디어를 떠올리기 어려웠던 문제로 답을 봤음에도 이해하는데 어려움이 있어서 꼭 복습이 필요!!

풀이 시간: 

---

---

1) 문제 해결 아이디어

예를 들어 수열 array = {4, 2, 5, 8, 4, 11, 15} 라면 가장 긴 증가하는 부분 수열은 {4, 5, 8, 11, 15} 이다.

이 문제는 가장 긴 감소하는 부분 수열을 찾는 문제로 LIS 알고리즘을 조금 수정하여 정답을 도출할 수 있다!

가장 먼저 입력받은 병사 정보의 순서를 뒤집고 최장 증가 부분 수열(LIS) 알고리즘을 수행하여 정답을 도출한다! 병사 정보의 순서를 뒤집는 이유는 LIS는 가장 긴 오름차순 수열을 찾는 것이지만 실제로 우리는 가장 긴 내림차순 수열을 찾아야 한다. 그러므로 이를 뒤집어 수행해야 한다!!

 

<최장 증가 부분 수열(LIS) 이란?>

원소가 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고 그 길이가 최대인 부분 수열을 최장 증가 부분 수열이라고 한다.

 

<최장 증가 부분 수열(LIS) 알고리즘>

앞에 있는 원소가 마지막 원소보다 작을 때에만 갱신!!

1. array[j]를 마지막 원소로 가지는 부분 수열의 최대 길이(d[j])에 마지막 원소(array[i])를 추가했을 때 길이

2. 마지막 원소(array[i])를 추가하지 않은 기존 길이

2가지 길이 중 더 큰 값을 채택한다.

 

[참고] https://chanhuiseok.github.io/posts/algo-49/

알고리즘 - 최장 증가 부분 수열(LIS) 알고리즘

 

2) 소스코드

n = int(input())  # 병사 수
array = list(map(int, input().split()))  # n명의 병사 전투력
array.reverse()  # 뒤집어 가장 긴 증가 부분 수열 문제로 변환
d = [1] * n

# 가장 긴 증가 부분 수열(LIS) 알고리즘 수행
for i in range(1, n):
  for j in range(i):
    # 앞에 있는 원소가 마지막 원소보다 작다면 갱신
    if array[j] < array[i]:
      d[i] = max(d[i], d[j] + 1)  
# 열외해야하는 최소 병사수
print(n - max(d))​

[출처] https://www.youtube.com/watch?v=5Lu34WIx2Us&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=7