[BOJ 25214] 백준 25214번 - 크림 파스타

		2022 인하대학교 프로그래밍 경진대회(IUPC) 풀이
A		[BOJ 25205] 경로당펑크 2077
B		[BOJ 25206] 너의 평점은
D		[BOJ 25208] 새벽의 탐정 게임
E		[BOJ 25209] 샤카샤카
F		[BOJ 25210] 정사각형 세기
G		[BOJ 25212] 조각 케이크
H		[BOJ 25214] 크림 파스타
I		[BOJ 25215] 타이핑

1. 문제

$25214$. 크림 파스타 (2022 인하대학교 프로그래밍 경진대회(IUPC) H번)

백준 25214번 - 크림 파스타 (https://www.acmicpc.net/problem/25214)

2. 풀이

$1\leq i \leq \ j \leq \vert A \vert$를 만족하는 정수 $i,\;j$에 대해서 수행한다는 것은, 임의의 두 index를 고르는 것이나 다름없다. 따라서 배열을 오름차순으로 정렬한 후에 두 개의 index를 골라도 아무 문제가 없다.

$j$는 뒤 index이고 $i$는 앞 index일 때, $A_j-A_i$의 최댓값을 구하는 문제이다. 따라서 $j$ index가 결정되고 나면, 그 이전 모든 index 중 A[index] 값이 가장 작은 index를 $i$로 두고 $A_j-A_i$를 구하면, 그 값이 최대값이다.

각 index마다 이전 index까지의 dp값(dp[i-1])과 현재 새로 만드는 값(A[i]-mini)을 비교해서 최대값으로 갱신한다. 또한, 다음 dp값을 구하기 위해 현재 index까지의 minimum 값도 같이 갱신해준다.

// mini: 이전 index까지의 A[i] 최솟값
dp[i] = max(dp[i - 1], A[i] - mini);

만들어낸 dp 배열이 정답이 된다.

3. 채점 결과

4. 회고

.

5. 코드