https://www.acmicpc.net/problem/14501
14501번: 퇴사
첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.
www.acmicpc.net
dp 문제이다
뒤에서 가는 생각은 했는데 그 이상은 구현해내지 못했다
n = int(input())
times = [], price = []
for i in range(n):
t, p = map(int,input().split())
times.append(t)
price.append(p)
dp = [-100]*(n+1)
maxvalue= 0
for i in range(n-1,-1,-1):
atTime = i + times[i]
if atTime <= n:
dp[i] = max(maxvalue,dp[atTime]+price[i])
maxvalue = dp[i]
else:
dp[i] = maxvaluehttps://www.acmicpc.net/problem/18353
18353번: 병사 배치하기
첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다.
www.acmicpc.net
n = int(input())
soldier = list(map(int,input().split()))
soldier.reverse()
dp = [1]*n
for i in range(1,n):
for j in range(0,i):
if soldier[j] < soldier[i]:
dp[i] = max(dp[i],dp[j]+1)
print(n-max(dp))이문제는 LIS 알고리즘을 알고 있어야 풀 수있었던 문제이다. 언제 한번 시간되는대로 LIS 알고리즘을 정리해야겠다.
dp 문제는 조금 어렵다;;
문제를 한 100문제는 풀어봐야 알 꺼 같다.
반응형