백준 17521번 [Byte Coin](C++) -yes6686- 티스토리

백준 문제 풀이: 17521 [Byte Coin]

---

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

문제 설명:

주어진 기간 동안 바이트 코인의 가격 변동을 알고 있을 때, 초기 현금을 최대한 활용하여 마지막 날에 최대의 현금을 보유하는 것이 목표입니다. 매일 코인을 매수하거나 매도할 수 있으며, 코인은 정수 단위로만 거래 가능합니다. 최종 날에는 모든 코인을 매도하여 현금화해야 합니다.

---

문제 해결 코드

// Byte Coin 문제 해결 코드
#include <iostream>
using namespace std;

int arr[16]; // 최대 16일 동안의 코인 가격 저장

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

    long long int n, w; // n: 기간(일 수), w: 초기 현금
    cin >> n >> w;

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

    int coin = 0; // 보유 코인 개수
    for (int i = 1; i < n; i++) {
        if (arr[i - 1] < arr[i]) {
            // 다음 날 가격이 오를 경우 매수
            if (coin != 0) continue; // 이미 코인을 보유 중이면 매수하지 않음
            coin = w / arr[i - 1];  // 최대한 매수
            w %= arr[i - 1];       // 잔액 계산
        } else if (arr[i - 1] > arr[i]) {
            // 다음 날 가격이 내릴 경우 매도
            w += coin * arr[i - 1]; // 현재 가격으로 전량 매도
            coin = 0;               // 코인 보유량 초기화
        }
    }

    // 마지막 날 보유 코인 전량 매도
    w += coin * arr[n - 1];
    cout << w << '\n';

    return 0;
}

---

코드 설명

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

• 핵심 알고리즘:
  • 그리디 알고리즘을 사용하여, 다음 날의 가격 변동에 따라 매수 또는 매도 시점을 결정합니다.
  • 가격이 상승하면 최대한 매수하고, 가격이 하락하면 전량 매도하여 이익을 극대화합니다.
• 구현 세부사항:
  • arr 배열에 코인 가격을 저장합니다.
  • coin: 현재 보유한 코인의 개수입니다.
  • 다음 날 가격이 오르면 최대한 매수합니다. 이미 코인을 보유 중이라면 추가 매수하지 않습니다.
  • 다음 날 가격이 내리면 보유한 모든 코인을 매도합니다.
  • 마지막 날 보유 코인을 모두 매도하여 최종 현금을 계산합니다.
• 시간 복잡도 분석:
  • 입력 처리: \(O(n)\)
  • 가격 변동에 따른 매수/매도 결정: \(O(n)\)
  • 전체 시간 복잡도: \(O(n)\)

---

결과

이 알고리즘은 주어진 가격 변동에 따라 최적의 매수 및 매도 시점을 찾아 최종 현금을 최대화합니다. 예를 들어:

• 입력: 10 24 및 가격 리스트 5 7 5 4 2 7 8 5 3 4
• 출력: 170

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!