# Chap 16. DP - Q34. 병사 배치하기

- Author: @mildsalmon
- Published: 2021-10-28
- Updated: 2021-10-28
- Source: http://blex.me/@mildsalmon/chap-16-dp-q34-%EB%B3%91%EC%82%AC-%EB%B0%B0%EC%B9%98%ED%95%98%EA%B8%B0
- Tags: 파이썬, 알고리즘, 한빛미디어, 나동빈, 코딩테스트, 문제, 풀이, 백준, dp, li

---

# 1. 병사 배치하기

- 난이도
	- 중하
- 풀이 시간
	- 40분
- 시간 제한
	- 1초
- 메모리 제한
	- 256 MB
- 출처
	- [18353번: 병사 배치하기 (acmicpc.net)](https://www.acmicpc.net/problem/18353)

### A. 📜 문제

위 백준 사이트에 접속하여 문제를 확인해주세요.
	
### B. 💡 내 답안

##### a. 😅 1차 시도 (실패)

```python

n = int(input())
array = list(map(int, input().split()))
dp = [array[-1]]

for i in range(n-2, -1, -1):
    if dp[-1] < array[i]:
        dp.append(array[i])

print(n - len(dp))

```

> 반례
>
> 7
> 15 11 4 3 10 2 1

##### b. 😊 2차 시도 (성공)

```python

n = int(input())
array = list(map(int, input().split()))
dp = [1] * n

array = array[::-1]

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)
            # print(i, "|", dp)

print(n - max(dp))

```

##### c. 🙄 회고

> 내 풀이

- 문제를 잘못 이해했다.
- 지금까지의 DP 문제들이 남아있는 수들의 합 중 최대를 구하라는 내용이었다. 그래서 이 문제도 **병사의 수가 최대가 되도록**을 **남아 있는 병사의 합이 최대가 되도록**이라고 잘못 해석해서 틀렸다.

> 반성

- 지레짐작하고 문제를 해석하지 말자. 문제에 제시된 내용을 해석해야한다.

### C. 🧐 문제 해설

> 이해한 내용을 바탕으로 작성했습니다.

![](https://static.blex.me/images/content/2021/10/28//2021_10_28_13_gyBKDlPEAoRVRoWsv3NL.jpg)

이런 경우 LIS (Longest Increasing Subsequence)를 사용한다.

LIS는 가장 긴 증가하는 부분 수열으로 증가하는 원소들의 가장 긴 부분집합을 찾는 알고리즘이다.

![](https://static.blex.me/images/content/2021/10/28//2021_10_28_13_7APhYO8qyWUQ16iLOjC6.jpg)

물론 다르지만, 삽입정렬이랑 비슷하게 생겼다.

##### a. 책 답안

[python-for-coding-test/4.py at master · ndb796/python-for-coding-test (github.com)](https://github.com/ndb796/python-for-coding-test/blob/master/16/4.py)

# 참고문헌

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

[18353번: 병사 배치하기 (acmicpc.net)](https://www.acmicpc.net/problem/18353). Baekjoon. (accessed Oct 28, 2021)