문제
백준 BOJ 2616 소형기관차
https://www.acmicpc.net/problem/2616
2616번: 소형기관차
첫째 줄에 기관차가 끌고 가던 객차의 수가 입력된다. 그 수는 50,000 이하이다. 둘째 줄에는 기관차가 끌고 가던 객차에 타고 있는 손님의 수가 1번 객차부터 차례로 입력된다. 한 객차에 타고 있
www.acmicpc.net
사용 알고리즘
풀이
누적합 + DP.
우선 소형 기관차가 최대로 끌 수 있는 객차의 수에 해당하는 길이의 구간마다 합을 구해 놓고
2차원 DP를 돌림.
dp[i][j]=max(dp[i-1][j],dp[i-m][j-1]+b[i]);dp[i][j] = i번째 객차까지 j개의 소형기관차를 썼을 때 최댓값.
728x90
'PS > BOJ' 카테고리의 다른 글
| 백준 BOJ 2109 순회강연 (0) | 2021.06.12 |
|---|---|
| 백준 BOJ 10800 컬러볼 (0) | 2021.06.11 |
| 백준 BOJ 11683 (0) | 2021.06.09 |
| 백준 BOJ 5582 공통 부분 문자열 (0) | 2021.06.08 |
| 백준 BOJ 20003 거스름돈이 싫어요 (0) | 2021.06.07 |