SWEA 1859번 백만 장자 프로젝트

문제를 보자마자 딱 떠오른 아이디어가 입력할 때 최대 값이 있는 인덱스를 구하고
최대 값 인덱스를 지나치면 최대 값 인덱스 + 1부터 다시 탐색을 해서 최대 값 인덱스를 구해주고

이를 반복하는 아이디어를 생각했다. 근데 이렇게 구해보니 역순으로 탐색하면 함수를 사용 안 하고 풀 수 있을 거 같아서 알아보니 많은 분들이 역순으로 문제를 해결했다고 해서 역순으로도 풀어봤는데 역순으로 푸는 게

MAX값을 찾는 함수를 쓰지 않아서인지 효율이 더 좋았다.

참고로 답을 구하는 변수는 int형 범위를 초과할수 있으니 long 또는 long long자료형을 써야한다

 

1. 순서대로 탐색한 코드

#include <iostream>
#include <vector>
#define INT long long
using namespace std;

INT Scan_Max(vector<INT> v, INT start) { // MAX값을 구하는 함수
	INT len = v.size();
	INT max = 0, max_index = 0;
	for (INT i = start; i < len; i++) {
		if (v[i] > max) {
			max = v[i];
			max_index = i;
		}
	}
	return max_index;
}

int main() {
	INT t;
	cin >> t;
	for (INT i = 0; i < t; i++) {
		vector<INT> v;
		INT profit = 0;
		INT n = 0, max = 0, max_index = 0;
		cin >> n;
		for (INT j = 0; j < n; j++) {
			INT num;
			cin >> num; v.push_back(num);
			if (max < v[j]) {
				max = v[j];
				max_index = j;
			}
		}
		for (INT j = 0; j < n; j++) {
			if (max_index == j) {
				max_index = Scan_Max(v, max_index + 1); MAX값의 다음 인덱스부터 검색
				continue;
			}
			profit += v[max_index] - v[j];
		}
		cout << "#" << i + 1 << ' ' << profit << '\n';
	}
	return 0;
}

2. 역순으로 탐색한 코드

#include <iostream>
#include <vector>
#define INT long long
using namespace std;

int main() {
	INT t;
	cin >> t;
	for (INT i = 0; i < t; i++) {
		vector<INT> v;
		INT profit = 0;
		INT n = 0, max = 0;
		cin >> n;
		for (INT j = 0; j < n; j++) {
			INT num;
			cin >> num; v.push_back(num);
		}
		int len = v.size();
		max = v[len - 1];
		for (INT j = len - 2; j >= 0; j--) {
			if (max < v[j]) {
				max = v[j];
			}
			profit += max - v[j];
		}
		cout << "#" << i + 1 << ' ' << profit << '\n';
	}
	return 0;
}