[백준/C++] 25214번 크림 파스타

백준

💡첫번째 아이디어

최솟값과 최댓값을 따로 저장해서 추가된 값이 최댓값보다 크거나 최솟값보다 작으면 최댓값과 최솟값을 업데이트해주는 방식을 생각했다.

이 방법으로는 1 <= i <= j <= |A| 라는 조건을 만족할 수 없었다.

 

 

💡두번째 아이디어

최솟값을 따로 저장하는 건 첫번째 아이디어와 동일하다. 다만 최댓값을 따로 저장하지 않고 (추가된 값 - 최솟값)과 dp배열의 이전 값을 비교해서 더 큰 것을 저장하는 방법을 생각해냈다.

 

예를 들어 예제 1번의 경우

추가 횟수(i)	추가한 값	최솟값	추가-최소	dp[i-1]	dp[i]
1	50	50	0	dp[0] = 0으로 초기화	0
2	100	50	50	0	50
3	70	50	20	50	50
4	110	50	60	50	60
5	10	10	0	60	60
6	100	10	90	60	90

위 표처럼 (추가-최소)과 dp[i-1] 중 더 큰 값이 dp[i]가 된다.

 

코드는 1트만에 성공!

맞았습니다!!

 

제출한 코드

#include <iostream>
using namespace std;

int dp[200000];
int min_num;

int main (){
    cin.tie(NULL);
    ios::sync_with_stdio(false);

    int t, x;
    cin >> t;
    for(int i=0; i < t; i++){
        cin >> x;
        if( i==0 ) {
            dp[0] = 0;
            min_num = x;}
        else {
            if ( x < min_num ) { min_num = x;}
            dp[i] = (x-min_num) > dp[i-1] ? (x-min_num) : dp[i-1];
        }
        cout << dp[i] << " " ;

    }
}