[Algorithm] 백준 - 크림 파스타 (25214번)

문제

[백준] 크림 파스타

사용 알고리즘

 

- 동적계획법 (Dynamic Programming)

해결방법

• dp[A배열 원소 개수] = (최대값 - 최소값)의 최대값
• A배열에 값이 들어올 때 마다 A의 원소중 최소값과 비교해 최소값을 체크해준다.
• 들어온 값 - 최소값 과 dp[i-1]을 비교해 더 큰 값을 dp[i]에 기록해준다.

예제 1

A 배열에 원소가 들어올 때마다의 상황을 표로 나타낸 것

• 50이 들어왔을 때
  • 원소 중 최소값 : 50
  • input 값과 최솟값의 차 : 0
  • 50이 들어오기 전까지 가장 (최대값-최소값)의 최대값 : 0
  • dp[1] = 0
• 100이 들어왔을 때
  • 원소 중 최소값 : 50
  • input 값과 최소값의 차 : 50 (100-50)
  • 100이 들어오기 전까지 가장 (최대값-최소값)의 최대값 (= dp[i-1]) : 0
  • dp[2] = 50

소스코드

사용언어 : C++

#include <iostream>
#include <algorithm>

using namespace std;

int A[200001];
int dp[200001];

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

    int min_plus_num = 1000000000;
    for(int i=1; i<=N; i++){
        cin >> A[i];
        
        if (A[i] < min_plus_num) {
            min_plus_num = A[i];
        }
        
        dp[i] = max(A[i] - min_plus_num, dp[i-1]);
        cout << dp[i] << " ";
    }
    
    return 0;
}

cin.tie & sync_with_stdio

https://nerdooit.github.io/2020/06/20/cpp_fastio.html

• cin.tie(NULL) => cout 하기 전 flushing 해제
  • untie 라고 생각하면 됨
• sync_with_stdio(false) => C stream 관리 중지
  • 속도 개선 but C관련 입출력 연산 사용 불가

 

한줄평

백준으로 넘어오니 stdio를 사용해야 하는데, php나 js는 어떻게 해야할지 잘 모르겠다. 일단 당분간으 c++을 쓰기로 ~