[C++][BOJ11501] 그리디 알고리즘

백준 그리디 11501

 

딱 보고 바로 떠오르진 않았다.

silver3으로 난이도는 낮은 문제

 

문제 풀이

중요한 포인트는 

i 번째 기준 i+1~마지막 중 max 값에서 팔면 최대라는 것이다.

이점을 이용해 풀어야하고 앞에서 부터 시작하면 i 마다 max가 달라지고

그 위치도 찾아줘야하기 때문에 복잡하다. 뒤에서 부터 시작해 max를 찾아 계산해주면 금방 풀린다.

 

 

시간 초과

#include <iostream>

using namespace std;

int main(){
	int T,N;
	scanf("%d",&T);
	while(T--){
		scanf("%d",&N);
		int answer = 0 ;
		int profit[N]={0,}; // 주식 판 이익 
		int stockPrice[N]={0,};//주식 가격 
		
		for(int i = 0 ; i < N;i++){  //시간 O(n) 
			scanf("%d",&stockPrice[i]); 
		}
		for(int i = N-1; i >=0 ;i--){
			for(int j = i-1 ; j>=0;j--){
				profit[j] = (profit[j] < stockPrice[i] - stockPrice[j] ) ?stockPrice[i] - stockPrice[j] : profit[j];
			}
		}
		for(int i = 0 ; i <N;i++) answer += profit[i];
		
		printf("%d\n",answer);
	}
	
}

이중 for문 때문에 시간 초과 나올것 같았지만 그래도 일단 풀어서 흐름 파악 해봤다.

 

정답 소스코드

#include <iostream>
using namespace std;
typedef long long ll;


int main(){
	int T,N;
	scanf("%d",&T);
	while(T--){
		scanf("%d",&N);
		int stockPrice[N]={0,};		
		for(int i = 0 ; i < N; i++){ 
			scanf("%d",&stockPrice[i]); 
		}
		
		int maxPrice = 0;
		ll answer = 0 ;
		for(int i = N-1; i >=0 ;i--){
			maxPrice = (maxPrice < stockPrice[i]) ? stockPrice[i] : maxPrice;
			answer += (maxPrice - stockPrice[i]);
		}		
		printf("%lld\n",answer);
	}
	
}

시간 복잡도 O(n)

어차피 for문 한번 쫙 돌기 때문에

맞길 바란다.

주의할점

제발 자료형 까먹지 말고, 출력할 때도 좀

마지막 printf에서 %lld로 안해서 몇번을 채점했다....

 

 

참고

https://tooo1.tistory.com/266

https://travelbeeee.tistory.com/15