https://www.acmicpc.net/problem/18353
18353번: 병사 배치하기
첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다.
www.acmicpc.net
문제 해결을 위한 과정
이 문제의 경우 가장 긴 증가하는 부분 수열 알고리즘을 알고 있다면 쉽게 해결할 수 있는 문제입니다. 해당 알고리즘에 대해서는 포스팅을 해 놓았습니다. 링크는 다음과 같습니다. https://bgspro.tistory.com/33?category=981927
가장 긴 증가하는 부분 수열 - Longest Increasing Subsequence (Python)
개념 가장 긴 증가하는 부분 수열 다시 말하면 LIS라고도 하는 이것은 다이나믹 프로그래밍 기법 중에 하나입니다. 말 그대로 어떤 수열이 주어졌을 때 해당하는 수열에서 오름차순 혹은 내림차
bgspro.tistory.com
먼저 문제의 경우 내림차순으로 배치를 하고자 한다고 합니다. 그러나 가장 긴 증가하는 부분 수열의 경우 오름차순에 대해서 하는 경우가 좀 더 일반적입니다. 따라서 입력받은 리스트를 reverse 함수를 이용해서 역순으로 바꾼 후 LIS 알고리즘을 사용하면 됩니다.
문제 해결을 위한 팁
LIS 알고리즘을 사용할 때 이중 for문을 통해 해결하는데 바깥 for문은 1번째 원소부터 n번째 원소까지, 안쪽 for문은 0번째 원소부터 바깥 for문의 인덱스까지 조회하는 방식으로 해결합니다.
소스코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
n = int(input())
data = [0]
ans = [0]*(2+n)
for i in range(1, n+1):
t, p = map(int, input().split())
data.append((i, t, p))
for i in range(1, n+1):
day, t, p = data[i]
if day + t <= n+1:
ans[i] += p
for j in range(day+t, n+1):
ans[j] = max(ans[day], ans[j])
print(max(ans))
|
cs |
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 알고리즘 1715: 카드 정렬하기 (Python) (0) | 2021.01.11 |
|---|---|
| 백준 알고리즘 2437: 저울 (Python) (0) | 2021.01.03 |
| 백준 알고리즘 14501: 퇴사 (Python) (1) | 2020.12.19 |
| 백준 알고리즘 1932: 정수 삼각(Python) (0) | 2020.12.18 |
| 백준 알고리즘 2110: 공유기 설치 (Python) (0) | 2020.12.18 |