문제

boj11501

처음에는 스택으로 풀었는데, 시간초과 날 수도 있겠다는 생각은 들었지만 틀렸을 줄은 몰랐다. 테케는 다 돌아가는데.. ^_ㅠ

그래서 스택 말고 입력받은 벡터 하나를 보는데, 뒤에서부터 봤더니 앞의 값들로 돌아갈 필요 없이 차익을 그냥 쭉쭉 더해주기만 하면 되었다. 그랬더니 O(N) 안에 풀 수 있었음!

10^6일 동안 관찰 + 주가는 최대 10^4원이기 때문에 sum 값은 int의 범위를 넘을 수 있다. 안전하게 long long으로 선언하자 (안 그래서 틀림)

구현

// BOJ 11501: 주식
#include <iostream>
#include <vector>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int T, N, i, tmp;
	cin >> T;

	while (T--) {
		vector<int> v;
		long long sum, max;
		sum = 0;

		cin >> N;
		for (i = 0; i < N; i++) {
			cin >> tmp;
			v.push_back(tmp);
		}

		max = v[N - 1];
		for (i = N - 1; i >= 0; i--) {
            if (v[i] > max) max = v[i]; // 최댓값이 갱신되는 경우
            else sum += max - v[i];
		}

		cout << sum << "\n";
	}
	return 0;
}

시간초과 날 것으로 예상했으나 아예 틀린 코드

#include <iostream>
#include <stack>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int T, N, i, tmp;
	cin >> T;

	while (T--) {
		cin >> N;

		stack<int> st;
		long long sum = 0;
		int top = 0;

		for (i = 0; i < N; i++) {
			cin >> tmp;

			if (st.empty()) st.push(tmp);
			else {
				if (st.top() <= tmp) st.push(tmp);
				else { // (st.top() > tmp) 
					top = st.top();
					while (!st.empty()) {
						sum += (top - st.top());
						st.pop();
					}
					st.push(tmp);
				}
			}
		}

		if (!st.empty()) {
			top = st.top();
			while (!st.empty()) {
				sum += (top - st.top());
				st.pop();
			}
		}
		cout << sum << "\n";
	}
	return 0;