1859. 백만 장자 프로젝트

 

처음 이 문제를 접했을 때, D2라는 수준을 감안하여 그냥 탐색해도 될까?라는 의문을 가지고 풀어 보았다. 운이 좋게도 이 솔류션으로도 해결이 가능했다. 하지만, 시간복잡도가 높기에 최적화를 해야될 것이다. 

Solution 

최고값을 안다면, 그 값이 나오기 전까지 계속해서 구매한다면, 1만큼이라도 이익이 발생한다.

1. 전체 값에서 최고값을 찾는다
2. 최고값까지 모든 순간에 구매를 한다
3. 최고값에 도착하면, 이후의 최고값을 다시 탐색한다
4. 탐색한 결과값으로 최고값을 갱신하고 위의 과정을 배열이 끝날 때까지 반복한다

 

Key Point

입력을 보면 배열의 최고 길이는 1000000이고, 최대 매매가는 10000입니다. 이렇게만 보아도 int의 범위를 넘어갑니다. 그렇기에 sum(answer)의 자료형을 long long로 변경해줘야합니다. 

 

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;

vector<int> list;
vector<int> vec;
int main(void) {
	freopen("inp.inp", "r", stdin);
	freopen("out.out", "w", stdout);

	int tc = 0;
	cin >> tc;
	for (int p = 0; p < tc; p++) {
		list.clear();
		int amount = 0;
		cin >> amount;
		int box;
		int max_point = 0;
		int max = 0;
		for (int i = 0; i < amount; i++) {
			cin >> box;
			list.push_back(box);
			if (max < box) {
				max = box;
				max_point = i;
			}
		}
		int sum = 0;
		for (int i = 0; i < amount; i++) {
			if (i==max_point) {
				max = 0;
				for (int j = i+1; j < amount; j++) {
					if (max < list[j]) {
						max = list[j];
						max_point = j;
					}
				}
			}else{
				sum += (max - list[i]);
			}
		}
		cout << "#" << p + 1 << " " << sum << endl;
	}



	return 0;
}

 

 

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LrsUaDxcDFAXc

SW Expert Academy