[Algorithm] C++/Python 백준 13416번 : 주식 투자

주식 투자는 미래의 이익을 기대하며 자본을 투입하는 행위이다. 하지만 매일매일의 시장 상황을 정확하게 예측하는 것은 어려운 일이다. 이번에 다룰 백준 13416번 문제는 주어진 주식 데이터에서 최대의 이익을 낼 수 있는 방법을 찾아내는 문제이다. 이 글에서는 문제의 상세한 설명과 함께 효율적인 알고리즘을 통해 문제를 해결해보도록 하겠다.

문제 : https://www.acmicpc.net/problem/13416

문제 설명

환규는 오늘부터 주식 투자를 하려고 한다. 그는 정보를 수집한 결과 A사, B사, C사 세 개의 회사에 투자하기로 결정했다. 그러나 그는 어떤 주식이 오를지, 떨어질지 예측하는 것이 아직은 힘들었다. 그래서 다음과 같은 투자 전략을 세웠다.

하루에는 최대 한 개의 회사 주식만 살 수 있다.
서로 다른 날에는 서로 다른 회사의 주식을 살 수 있지만, 하루에는 최대 한 개의 회사 주식만 구매한다.
매일 장이 열리기 전에 그날 주식을 살 회사를 정하고, 장이 열릴 때 해당 회사의 주식을 산다.
장이 닫힐 때 그날 산 주식을 모두 판다.
만약 세 회사 중 어느 곳도 수익이 날 것 같지 않으면 주식을 구매하지 않아도 된다.

환규는 주식을 처음 해보기 때문에 이 전략으로 주식 투자를 했을 때 얼마나 이익을 낼 수 있는지 궁금해졌다. 그래서 투자하려는 회사들의 지난 N일 동안의 주식 데이터를 이용해 N일 동안 위의 규칙을 지키며 주식 투자를 했을 때 과연 얼마를 벌 수 있는지 계산해 보기로 했다.

환규는 각 회사별로 장이 열릴 때 주식을 사고, 장이 닫힐 때 모두 팔았을 경우 매일 얼마를 벌 수 있었는지 정리했다. 다음은 N = 4일 때 환규가 정리한 데이터를 나타내는 표이다.

날짜	A사	B사	C사
1일	500	800	200
2일	300	0	300
3일	-100	-200	-400
4일	600	200	300

양수는 이익을, 음수는 손해를 나타내며, 0은 이익도 손해도 없음을 의미한다.
예를 들어, 1일째에 A사의 주식을 장이 열릴 때 사고, 장이 닫힐 때 팔면 500의 이익을 얻을 수 있었다.
3일째에 C사의 주식을 장이 열릴 때 사고, 장이 닫힐 때 판다면 400의 손해가 발생한다.

데이터를 분석하던 환규는 자신이 정리한 데이터를 이용해서 N일 동안 규칙을 지키면서 매일 최적의 투자를 할 경우 최대 얼마를 벌 수 있었는지 궁금해졌다.

예를 들어 위 표에서:
- 1일째에는 B사의 주식을 사면 가장 많은 이익을 남길 수 있다 (800).
- 2일째에는 A사 또는 C사의 주식을 사면 가장 많은 이익을 남길 수 있다 (300).
- 3일째에는 어떤 주식을 사도 손해가 나므로 주식을 사지 않는다.
- 4일째에는 A사의 주식을 사면 된다 (600).
이렇게 주식 투자를 할 경우 환규는 800 + 300 + 0 + 600 = 1700으로, 최대 1700의 이익을 남길 수 있다.

문제: 환규가 N일 동안 위의 규칙을 지키며 최적의 투자를 했을 때 얻을 수 있는 최대 이익을 계산하는 프로그램을 작성하시오.

접근 방식

이 문제는 각 날마다 선택할 수 있는 가장 큰 이익을 고르는 그리디(Greedy) 알고리즘으로 풀린다. 매일 세 회사의 손익 중 가장 큰 값을 찾고, 그 값이 양수일 때만 총 이익에 더하며, 0 이하이면 그날은 투자를 건너뛴다. 입력은 테스트 케이스 수 T로 시작하고, 각 케이스는 일수 N과 N줄의 세 정수로 이어지므로 입력을 읽는 순서대로 한 번 훑으면 끝난다. 전체 시간 복잡도는 O(N)이고 추가 메모리는 합계 변수 하나뿐이라 공간 복잡도는 O(1)이다.

그리디가 최적인 이유

그리디 풀이는 “각 날의 최선을 모으면 전체의 최선이 된다"는 주장에 기대므로 이유를 짚어두어야 한다. 이 문제의 규칙은 장이 닫힐 때 산 주식을 모두 판다는 것이다. 따라서 어느 날의 선택은 보유 자산, 다른 날의 선택, 남은 자금에 아무 영향을 주지 않고 그날의 수익 하나에만 반영된다. 총 이익은 날짜별 수익의 합이며, 날마다 고를 수 있는 값의 집합이 서로 독립이다. 독립된 항들의 합을 최대로 만들려면 각 항을 따로 최대화하면 된다. 어느 한 날에 최댓값보다 작은 값을 고르면 합이 그만큼 줄어들 뿐이고, 그것을 보상해줄 다른 날의 이득은 존재하지 않는다. 이것이 교환 논증(exchange argument)의 가장 단순한 형태다.

이 독립성은 규칙에 의존한다는 점을 기억해야 한다. 예를 들어 “같은 회사를 연속으로 사지 못한다” 같은 제약이 붙으면 어제의 선택이 오늘의 선택지를 줄이므로 날짜 간 독립이 깨지고, 그리디는 틀릴 수 있으며 DP가 필요해진다. 이 문제가 그리디로 풀리는 것은 알고리즘이 영리해서가 아니라 구조가 단순해서다.

흔한 실수

가장 흔한 실수는 세 회사 중 최댓값이 음수일 때도 합산하는 것이다. 표의 3일째처럼 모든 회사가 손해를 보는 날은 구매하지 않아도 되므로 그날의 기여는 0이어야 한다. 최댓값이 0인 날도 더하나 안 더하나 결과가 같으므로 > 0과 >= 0은 모두 정답이다. 다른 하나는 “하루에 한 회사만 살 수 있다"를 무시하고 양수인 회사를 모두 더하는 것으로, 표의 1일째에서 500 + 800 + 200을 더하면 1500이 되어 정답 800과 어긋난다.

C++ 코드와 설명

C++ 풀이는 std::max의 초기화 리스트 버전으로 세 값의 최댓값을 한 번에 구한다. 합계는 long long으로 두었다. 일수가 많아지면 일별 이익의 합이 int 범위를 넘을 수 있으므로, 제약을 일일이 계산하지 않고 넉넉한 자료형을 택하는 편이 비용이 거의 없는 안전장치다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream> // 표준 입출력 사용
#include <algorithm> // max 함수 사용
using namespace std;

int main() {
    int T; // 테스트 케이스 수
    cin >> T; // 테스트 케이스 입력
    while (T--) {
        int N; // 주식 데이터의 일수
        cin >> N; // 일수 입력
        long long totalProfit = 0; // 총 이익 초기화
        for (int i = 0; i < N; ++i) {
            int A, B, C; // 각 회사의 손익
            cin >> A >> B >> C; // 손익 입력
            int maxProfit = max({A, B, C}); // 세 회사 중 최대 이익
            if (maxProfit > 0) { // 최대 이익이 양수인 경우
                totalProfit += maxProfit; // 총 이익에 더하기
            }
        }
        cout << totalProfit << endl; // 결과 출력
    }
    return 0;
}

C++ without library 코드와 설명

표준 라이브러리의 max와 iostream 없이 C 스타일로 쓴 버전이다. 최댓값은 A로 시작해 B, C와 차례로 비교하며 갱신하고, 입출력은 scanf/printf를 쓴다. 출력 서식 %lld가 long long과 짝이 맞아야 한다는 점만 주의하면 된다. C++ 버전이 endl로 매 케이스마다 버퍼를 비우는 것과 달리 이쪽은 개행 문자만 출력하므로, 케이스가 많을 때 입출력 비용이 조금 작다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <stdio.h> // 표준 입출력 사용

int main() {
    int T; // 테스트 케이스 수
    scanf("%d", &T); // 테스트 케이스 입력
    while (T--) {
        int N; // 주식 데이터의 일수
        scanf("%d", &N); // 일수 입력
        long long totalProfit = 0; // 총 이익 초기화
        for (int i = 0; i < N; ++i) {
            int A, B, C; // 각 회사의 손익
            scanf("%d %d %d", &A, &B, &C); // 손익 입력
            int maxProfit = A; // 최대 이익 초기화
            if (B > maxProfit) maxProfit = B; // B와 비교하여 최대값 갱신
            if (C > maxProfit) maxProfit = C; // C와 비교하여 최대값 갱신
            if (maxProfit > 0) { // 최대 이익이 양수인 경우
                totalProfit += maxProfit; // 총 이익에 더하기
            }
        }
        printf("%lld\n", totalProfit); // 결과 출력
    }
    return 0;
}

Python 코드와 설명

Python 풀이는 내장 max와 map(int, input().split())로 한 줄을 읽는 관용구를 쓴다. 파이썬의 정수는 크기 제한이 없어 오버플로를 걱정할 필요가 없고, 구조는 C++ 버전과 같다. 입력이 매우 크면 sys.stdin.readline으로 바꾸는 것이 보통이지만, 이 문제의 한 줄에 세 정수인 입력 형태에서는 input()으로 충분하다고 판단했다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
T = int(input())  # 테스트 케이스 수 입력
for _ in range(T):
    N = int(input())  # 주식 데이터의 일수 입력
    total_profit = 0  # 총 이익 초기화
    for _ in range(N):
        A, B, C = map(int, input().split())  # 각 회사의 손익 입력
        max_profit = max(A, B, C)  # 세 회사 중 최대 이익
        if max_profit > 0:  # 최대 이익이 양수인 경우
            total_profit += max_profit  # 총 이익에 더하기
    print(total_profit)  # 결과 출력

코너 케이스

케이스	설명	처리 방법
모두 음수인 날	어느 회사를 사도 손해	최댓값이 양수가 아니므로 0을 더한다
최댓값이 0인 날	이익도 손해도 없음	더해도 안 더해도 결과가 같다
전 기간이 손해	모든 날이 위와 같음	총 이익 0을 출력한다
테스트 케이스 다수	T개의 케이스가 이어짐	케이스마다 합계를 0으로 초기화한다
같은 날 최댓값 동률	표의 2일째 A사와 C사	값이 같으므로 어느 쪽을 골라도 합이 같다

정리

이 문제의 핵심은 코드가 아니라 “날짜별 선택이 서로 독립이다"라는 관찰이다. 장 마감 시 전량 매도 규칙 때문에 합을 항별로 최대화하면 되고, 그래서 O(N) 그리디가 정답이 된다. 같은 형태의 문제에서 제약이 날짜 사이를 이어 붙이면 그리디 대신 DP를 의심해야 한다. 이 글을 읽은 뒤에는 그리디가 성립하는 조건을 독립성으로 설명하고, 연속 구매 금지 같은 변형에서 왜 깨지는지 말할 수 있어야 한다.