Prefix Sum
백준 BOJ 2616 소형기관차
문제 백준 BOJ 2616 소형기관차 https://www.acmicpc.net/problem/2616 2616번: 소형기관차 첫째 줄에 기관차가 끌고 가던 객차의 수가 입력된다. 그 수는 50,000 이하이다. 둘째 줄에는 기관차가 끌고 가던 객차에 타고 있는 손님의 수가 1번 객차부터 차례로 입력된다. 한 객차에 타고 있 www.acmicpc.net 사용 알고리즘 Dynamic programming Prefix sum 풀이 누적합 + DP. 우선 소형 기관차가 최대로 끌 수 있는 객차의 수에 해당하는 길이의 구간마다 합을 구해 놓고 2차원 DP를 돌림. dp[i][j]=max(dp[i-1][j],dp[i-m][j-1]+b[i]); dp[i][j] = i번째 객차까지 j개의 소형기관차를 썼을 때 최댓값.
백준 BOJ 10800 컬러볼
문제 백준 BOJ 10800 컬러볼 https://www.acmicpc.net/problem/10800 10800번: 컬러볼 첫 줄에는 공의 개수를 나타내는 자연수 N이 주어진다(1 ≤ N ≤ 200,000). 다음 N개의 줄 중 i번째 줄에는 i번째 공의 색을 나타내는 자연수 Ci와 그 크기를 나타내는 자연수 Si가 주어진다(1 ≤ Ci ≤ N www.acmicpc.net 사용 알고리즘 Implementation Sorting Prefix sum 풀이 {크기, 색깔, index} 를 원소로 하는 3진 pair를 만들어 크기를 기준으로 정렬. 누적 합을 구하면서 색깔별 누적 합도 따로 구해줌. 같은 색깔 + 같은 크기일 경우에도 따로 처리. 아이디어 구상은 쉬우나 예외 처리 부분이 신경 쓸 게 많았음.