[BaekJoon] 18353번 : 병사 배치하기

18353번 : 병사 배치하기

우선 결론만 말하자면 [BaekJoon] 백준 11053번 : 가장 긴 증가하는 부분 수열 과 똑같은 문제이다.

가장 긴 감소하는 부분 수열 길이를 구한 뒤 전체 길이에서 빼주면 된다.

그런데.. 이 생각을 도저히 하지 못했다.

열외해야 하는 병사의 수를 구하는 것에 집중하는 바람에 반대로 구하는 방법을 생각하지 못했다.

알고리즘 시간에 배웠다! A 라는 답을 구하기 어려우면 B 라는 답을 구해 A 를 구하는 방법도 생각 해보라고..

이 문제가 바로 그 문제다.

열외해야 하는 병사의 수는 가장 긴 감소하는 부분수열에 포함 되지 않는 원소이다.

하지만 직접적으로 열외해야 하는 병사의 수는 구하기 어렵다.

때문에 B 라는 답, 즉 가장 긴 감소하는 부분수열 길이를 구한 뒤 전체 수열길이에서 B 를 빼주면 A 를 구할 수 있다.

아직 이런식으로 문제에 어떤 알고리즘을 사용해야 하는지 생각하는게 어렵다.

만약 문제가 직접적으로 가장 긴 감소하는 부분수열의 길이를 구하라고 했다면 구할 수 있었을 것이다..

수능 공부할 때도 꼬아서 나온 문제는 잘 못 풀었는데 여전하다 ㅡㅡ;

---

def solution():
	dp = [1] * n

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

	return n - max(dp)


if __name__ == '__main__':
	n = int(input())
	arr = list(map(int, input().split()))
	print(solution())