백준 11501번 주식

사용한 알고리즘: DFS

dfs를 돌리면서 남은 기간중 가장 큰 값을 계속 최신화해주었습니다.

temp = 남은 기간중 최대값 / point = 가장 큰 값의 위치 이라 놓고,
현 위치부터 point까지 for 구문을 돌리며
구하고자 하는 값에 temp-arr[i] 값을 더해주었습니다.

만약 point != N-1(맨끝)  이면 다시 dfs 를 돌려주었습니다.

주의할 점은 구하고자 하는 값을 long long으로 놓는 것이었습니다.

	#include <bits/stdc++.h>
	using namespace std;
	#define pii pair<int, int>
	int T, N;
	int arr[1000001];
	long long ans;
	long long GetAns(int curr){
	long long result = 0;
	int temp = 0;
	int Point = 0;
	for (int i = curr; i < N; ++i)
	if(arr[i]>=temp){
	temp = arr[i];
	Point= i;
	}
	for (int i = curr; i < Point; ++i)
	result += (temp-arr[i]);
	if(Point<N-1) result+=GetAns(Point+1);
	return result;
	}
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> T;
	while(T--){
	memset(arr,0,sizeof(arr));
	cin >> N;
	for (int i = 0; i < N; ++i)
	cin >> arr[i];
	cout << GetAns(0) << '\n';
	}
	return 0;
	}

view raw BOJ 11501.cpp hosted with ❤ by GitHub