https://www.acmicpc.net/problem/18353
18353번: 병사 배치하기
첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다.
www.acmicpc.net
> 문제 풀이 아이디어
DP로 풀 수 있는 문제이다.
해당 문제에서 dp에는 최대 병사 인원 수가 들어간다.
푸는 논리는 다음과 같다.
- 우선 dp를 병사 수만큼 1로 초기화한다.
- 1 번째 병사는 0 번째 병사보다 전투력이 작으므로 연산을 수행한다. (0 번째 병사의 인원수 +1) 과 (1번째 병사의 인원 수) 중 큰 값을 dp[1]에 넣어준다.
- 2 번째 병사는 0 번째 병사보다 전투력이 작으므로 마찬가지로 동일한 연산을 수행하면 dp[2]엔 2가 들어간다. 또한 1 번째 병사보다도 전투력이 작으므로 동일한 연산을 수행하면 dp[2]엔 3이 들어간다.
- 3 번째 병사에 대해서도 동일한 연산을 수행한다. 다만 2 번째 병사의 전투력이 3 번째 병사의 전투력보다 크므로 해당 경우에는 연산을 수행하지 않는다.
...
- 마지막 병사까지 연산하면 dp값은 [1,2,3,3,4,5,5]가 나온다. 즉 최대 병사 인원 수가 5명이므로 빠져야하는 병사 수는 7-5=2명이다.
> 포인트
내림차순으로 정렬해야하기 때문에 "현재 값이 이전 값보다 작느냐"를 연산 조건으로 세워준다.
만일 작다면 병사의 최대 인원 수를 연산해주고, 크다면 아무 연산도 하지 않는다.
최대 인원 수를 dp에 넣어줘야하기 때문에, 연산방법은 연산 수행 조건을 만족하는 이전 dp값들(병사 인원 수) 중 가장 큰 인원 수에, 현재 병사 한 명을 더해준 값이 나올 수 있도록한다.
> 코드
'python > 알고리즘 문제풀이' 카테고리의 다른 글
| [백준 | 파이썬3] 18352 특정 거리의 도시 찾기 (0) | 2022.07.07 |
|---|---|
| [백준 | 파이썬3] 1874 스택 수열 (0) | 2022.02.28 |
| [백준 | 파이썬3] 10814 나이 순 정렬 (0) | 2022.02.23 |
| [프로그래머스 | 파이썬3] 약수의 개수와 덧셈 (0) | 2021.12.09 |
| [프로그래머스 | 파이썬3] 실패율 - 정렬 (0) | 2021.12.08 |