[D2] 1859. 백만 장자 프로젝트

입력) 

자연수 N(2 ≤ N ≤ 1,000,000)

각 날의 매매가를 나타내는 N개의 자연수들(10,000이하)

 

출력)

최대 이익을 출력

 

입, 출력 분석)

최대 이익 = 10,000이하의 자연수들 * 1,000,000개 

최악의 경우 10,000,000,000이 나온다.

자료형	범위
int (4byte)	-2^31‬-1 ~ 2^31-1 = -2,147,483,648 ~ 2,147,483,647
long long (8byte)	-2^63-1 ~ 2^63-1 = –9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807

 

예시 분석)

3
3
10 7 6
3
3 5 9
5
1 1 3 1 2

 

1	2	3	4	5
1	1	3	1	2

위 경우 2번째 날까지 사고(cost:2), 3번째 날에 팔았고(profit:3*2 - cost),

4번째 날에 사고(cost:1), 5번째 날에 팔았다면(profit:1*2 - cost),

이익은 (6-2)+(2-1) = 4+1 = 5이다.

1	2	3	4	5	6
1	1	3	1	1	4

위 경우  5번째 날까지 사고(cost:7), 6번째 날에 팔았다면(profit:4*5 - cost),

이익은 13이다.

 

핵심)

들어오는 수열에서 가장 큰 수를 찾아서,

'가장 큰 수 * 이전 수열까지의 개수' - '그 이전의 수열까지의 합'을 구하고,

이후 수열부터 이런 과정을 수열이 끝날 때까지 반복하면 된다.

 

핵심은 알았는데 1,000,000개의 수열에서 어떻게 제일 큰 수를 먼저 찾지..?
한참 고민하다가 힌트를 얻었다..ㅎ https://blog.naver.com/hongjg3229/221467996183

뒤에서부터 큰 수를 갱신해오면서 이익을 더해주니 금방 PASS 했다.

 

구현)

#include<iostream>
using namespace std;

int arr[1000000];
int N;

int main(int argc, char** argv){
	int test_case;
	int T;
	cin >> T;
	for (test_case = 1; test_case <= T; ++test_case) {
		scanf("%d", &N);
		for (int i = 0; i < N; ++i){
			scanf("%d", &arr[i]);
		}
		long long profit = 0;
		int maxIdx = N-1;
		for (int idx = N-2; idx >= 0; --idx){
			if(arr[idx] < arr[maxIdx]) profit += arr[maxIdx] - arr[idx];
			else maxIdx = idx;
		}
		printf("#%d %lld\n", test_case, profit);
	}
	return 0;
}

상반기 끝나고 한 달 놀고 왔더니 머리가 단단히 굳은 것 같다....

앞으로 더 꾸준히 하면 된다! 아자아자!