1. 병사 배치하기
- 난이도
- 중하
- 풀이 시간
- 40분
- 시간 제한
- 1초
- 메모리 제한
- 256 MB
- 출처
A. 📜 문제
- 중하
- 40분
- 1초
- 256 MB
위 백준 사이트에 접속하여 문제를 확인해주세요.
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. 🧐 문제 해설
이해한 내용을 바탕으로 작성했습니다.
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. 🧐 문제 해설
이해한 내용을 바탕으로 작성했습니다.
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))
내 풀이
- 문제를 잘못 이해했다.
- 지금까지의 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)
Ghost