[백준/Baekjoon] 1487 물건 팔기 C++ :: Brute Force

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

1487번: 물건 팔기

---

1. Logic

n의 범위가 50이기 때문에 완탐을 돌려도 시간복잡도가 안넘는다!

 

먼저 입력을 받은 후 입력값을 오름차순으로 정렬한다. 그럼 작은 가격부터 기준을 잡고, 기준으로부터 배열끝까지 돌면서 가격을 계산한다. 모든 수를 다 돌게되면 시간복잡도도 넘을 뿐더러, 기준보다 작으면 선택받지 못하기 때문에 무조건 선택받을 수 있게 배열의 가격을 기준으로 잡는것이다. 가격의 기준을 잡는 부분이 첫번째 for문에 해당된다.

 

---

2. Code

#include<bits/stdc++.h>

using namespace std;

vector<pair<int, int>> input;
int n;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    
    for(int i = 0; i < n; i++) {
        int product, delivery;
        cin >> product >> delivery;
        
        input.push_back({product, delivery});
    }
    
    sort(input.begin(), input.end());
    
    int maxCost = 0;
    int maxProfit = 0;
    
    for(int i = 0; i < n; i++) {
        int sum = 0;
        for(int j = i; j < n; j++) {
            int curProfit = input[i].first - input[j].second;
            if(curProfit > 0) sum += curProfit;
        }
        if(maxProfit < sum) {
            maxProfit = sum;
            maxCost = input[i].first;
        }
    }
    
    cout << maxCost;
}

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐

728x90