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

1. 병사 배치하기

A. 📜 문제

위 백준 사이트에 접속하여 문제를 확인해주세요.

B. 💡 내 답안

a. 😅 1차 시도 (실패)

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차 시도 (성공)

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. 🧐 문제 해설

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

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

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

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

a. 책 답안

python-for-coding-test/4.py at master · ndb796/python-for-coding-test (github.com)

참고문헌

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

18353번: 병사 배치하기 (acmicpc.net). Baekjoon. (accessed Oct 28, 2021)

이 글이 도움이 되었나요?

신고하기
0분 전
작성된 댓글이 없습니다. 첫 댓글을 달아보세요!
    댓글을 작성하려면 로그인이 필요합니다.