[백준/Baekjoon] 2236 칩 만들기 C++ :: Greedy

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

2236번: 칩 만들기

---

1. Logic

선을 하나의 칩에 연결하면 제곱, 두개의 칩에 연결하면 연결한 두 칩의 중요도를 제곱한다.

어떤 경우든 항상 제곱하는게 이득이기 때문에 그냥 정렬해서 큰거만 k개만큼 뽑아주면 된다

풀면서도 이게 맞나 싶었다ㅋㅋㅋㅋㅋㅋ

---

2. Code

#include<bits/stdc++.h>

using namespace std;

int n, k;

vector<pair<int, int>> input;
queue<int> q;
int trace[51];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	cin >> n >> k;
	
	for(int i = 1; i <= n; i++) {
	    int priority;
	    cin >> priority;
	    
	    input.push_back({priority, i});
	}
	
	sort(input.begin(), input.end(), greater<pair<int, int>>());
	
	for(int i = 0; i < k; i++) {
	    trace[input[i].second] = input[i].second;
	    
	    q.push(input[i].second);
	}
	
	while(!q.empty()) {
	    cout << q.front() << '\n';
	    q.pop();
	}
	
	for(int i = 1; i <= n; i++) {
	    cout << trace[i] << '\n';
	}
}

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

728x90