16494

https://xkdlaldfjtnl.tistory.com/194

22.03.15 풀이

백준 16494 가장 큰 값

위 링크 보세요

 

-----------------------------------------------------------------------------------------------------------------------
-----------------------------------------------------------------------------------------------------------------------

-----------------------------------------------------------------------------------------------------------------------

혹시나 구글링하고 실망할까봐 문제번호만 적음

 

일단 M개를 선택하고 나서 최대인거를 골라야 함 

 

근데 M개를 어떤 식으로 골라야 할까 ..

 

브루트 포스의 시간복잡도를 계산 해보니깐 좀 애매한 것 같기도 하고, 구현도 좀 까다롭고 해서 일단 패스하고 다른 생각을 하는 중

 

아무리 봐도 pq를 잘 굴리면 될거 같은데 일단 안 떠오른다 

근데 pq에 넣으면 가장 큰 순서로 찾아서 내가 원하는 수는 찾기 어려울 거 같다 

 

일단 아닌 코드

#include<iostream>
#include<queue>
#include<utility>
using namespace std;

int N, M;
int num[21];
int pre_sum[21][21];
bool check[21];
priority_queue< pair <int, pair<int,int> > > pq;

int main() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >> num[i];
	}
	for (int i = 0; i < N; i++) {
		for (int j = i; j < N; j++) {
			if (i == j) {
				pre_sum[i][j] = num[i];
				continue;
			}
			pre_sum[i][j] = pre_sum[i][j - 1] + num[j];
		}
	}

	int ans = 0;

	for (int i = 0; i < N; i++) {
		for (int j = i; j < N; j++) {
			pq.push(make_pair(pre_sum[i][j], make_pair(i,j)));
		}
	}
	int n = 0;
	while(n<M) {
		pair<int, int> p = pq.top().second;
		bool done = true;
		for (int a = p.first; a <= p.second; a++) {
			if (check[a]) {
				done = false;
				break;
			}
		}
		if (done) {
			ans += pq.top().first;
			for (int a = p.first; a <= p.second; a++)
				check[a] = true;
			cout << p.first << " " << p.second << '\n';
			n++;
		}
		pq.pop();
	}
	cout << ans << '\n';
}