백준 25644번 [최대 상승](C++) -yes6686- 티스토리

백준 문제 풀이: 25644 [최대 상승]

---

문제 링크: https://www.acmicpc.net/problem/25644

문제 설명:

주식의 가격 변동이 시간 순서대로 주어졌을 때, 특정 시점에서 주식을 매수한 후 다른 시점에서 매도했을 때 얻을 수 있는 최대 이익을 구하는 문제입니다.

주어진 가격 배열에서 매수와 매도 시점을 선택하여 최대 이익을 계산해야 하며, 이익이 발생하지 않는 경우 이익은 0으로 출력됩니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

int arr[200001]; // 주식 가격 배열

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

    int n;
    cin >> n; // 주식 가격의 개수

    for (int i = 0; i < n; i++) {
        cin >> arr[i]; // 주식 가격 입력
    }

    int minPrice = arr[0]; // 현재까지의 최소 매수 가격
    int maxProfit = 0;     // 최대 이익

    for (int i = 1; i < n; i++) {
        if (arr[i] > minPrice) {
            // 현재 가격에서 이익 계산 및 최대값 갱신
            maxProfit = max(maxProfit, arr[i] - minPrice);
        } else {
            // 최소 매수 가격 갱신
            minPrice = arr[i];
        }
    }

    // 최대 이익 출력
    cout << maxProfit;
    return 0;
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명.

• 핵심 알고리즘:
  • 1차 순회를 통해 배열의 각 원소를 검사하며 최대 이익을 계산합니다.
  • 현재까지의 최소 매수 가격 minPrice를 유지하면서, 현재 가격에서의 이익을 계산하여 최대값을 갱신합니다.
• 구현 세부사항:
  • minPrice: 배열을 순회하며 현재까지의 최소값을 기록합니다.
  • 이익 계산: arr[i] - minPrice를 통해 현재 가격에서 매수 시점까지의 이익을 계산합니다.
  • maxProfit: 최대 이익을 기록하며, 최종적으로 최대값을 출력합니다.
• 시간 복잡도 분석:
  • 배열을 한 번 순회하므로 O(n)의 시간 복잡도를 가집니다.
  • 공간 복잡도는 O(1)로 추가 배열이나 자료구조를 사용하지 않습니다.

---

결과

주어진 주식 가격 배열에서 최대 이익을 정확히 계산하며, 이익이 발생하지 않는 경우 0을 출력합니다.

해당 문제에 대한 다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!