그리디(1) - 로프, 잃어버린 괄호, 주식

https://www.acmicpc.net/problem/2217

2217번: 로프

#include <bits/stdc++.h>
using namespace std;
int g[100005],mx;
int main(){
	ios::sync_with_stdio(0); 
	cin.tie(0);
	int n; cin>>n;
	for(int i=0;i<n;i++) cin>>g[i];
	sort(g,g+n,greater<>());
	for(int i=0;i<n;i++){
		mx=max(mx,g[i]*(i+1));
	}
	cout<<mx;
	return 0;
}

내림차순으로 정렬하고, 큰 하중을 버틸 수 있는 로프부터 순차적으로 고른다고 생각한다.

15 10이 있다면 들 수 있는 최대 중량은 숫자의 최솟값에 수의 갯수를 곱한 값이다.

즉 10*2=20

20 15 10이 있다면 30이 된다.

---

https://www.acmicpc.net/problem/1541

1541번: 잃어버린 괄호

-가 나온다면 그 이후부터는 숫자들을 더할 필요 없이 다 빼면 된다. 

5-3+1-3+2 라면 괄호로 - 이후의 숫자들을 묶으면 다 - 처리되므로 +를 할 필요가 없다는 것이다.

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int sign=1,ans=0,temp=0;
    string str; cin>>str;
    for(char c : str){
        if(c=='+'||c=='-'){
            ans+=(temp*sign);
            if(c=='-') sign=-1;
            temp=0;
        }
        else{
            temp=temp*10+(c-'0');
        }
    }
    ans+=(temp*sign);
    cout<<ans;
    return 0;
}

---

https://www.acmicpc.net/problem/11501

11501번: 주식

저점에 사고 고점에 팔아야 한다. 고점이란 현재 산 값 이후의 값들 중 가장 가치가 높은 값을 말하는데, 그렇기 때문에 0부터 N-1까지 탐색하면 O(N^2)이므로 시간초과가 발생한다.

그러므로 거꾸로 탐색해야 한다. 

 

6 4 3 7 1 2 5 3 2 를 거꾸로 탐색해보자거꾸로 탐색하며 최댓값을 갱신하고, 최댓값보다 작은 값이 있으면 사고 판다.저기서 첫 번째 최댓값은 5가 될 것이고, 2는 5보다 작으므로 2에 사고(-2) 5에 판다(+5) -> 3다음의 1은 5보다 작으므로 1에 사고(-1) 5에 판다.(+5) -> 4이 작업을 반복하면 최댓값을 구할 수 있다.

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int k; cin>>k;
    while(k--){
        int n; cin>>n;
        vector<int> arr(n);
        for(int i=0;i<n;i++) cin>>arr[i];

        long long ans=0;
        int maxidx=n-1;
        for(int i=n-2;i>=0;i--){
            if(arr[i] < arr[maxidx]) ans+=(arr[maxidx]-arr[i]);
            else maxidx=i;
        }

        cout<<ans<<'\n';
    }
    return 0;
}