백준17224 - APC는 왜 서브태스크 대회가 되었을까?

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

17224번: APC는 왜 서브태스크 대회가 되었을까?

그리디 문제다. 역량보다 쉬운 sub2의 문제를 최대한 많이 풀고 풀 수 있는 문제의 수에서 sub2를 풀어낸 수를 빼서 역량보다 쉬운 sub1의 문제를 푼다. 

 

#include <iostream>
#include <utility>
#include <set>
#include <vector>
using namespace std;

int N, L, K; //N은 문제 수(문제에 번호라고 생각), L은 역량, K는 풀 수 있는 문제의 수
int sub1, sub2; //sub1의 난이도, sub2의 난이도
int cnt = 0; //현재 푼 문제의 갯수
int score; //획득한 점수
vector<pair<int, int>> vp; //sub1과 sub2의 난이도를 벡터에 저장
pair<int, int> p; //점수를 pair로 저장
set<int> st; //풀어낸 문제의 번호

int main() {
	cin >> N >> L >> K;

	//N개 만큼 문제의 번호에 따라 난이도를 입력
	for (int i = 1; i <= N; i++) {
		cin >> sub1 >> sub2;
		p.first = sub1; //pair의 첫번째 값은 sub1
		p.second = sub2; //pair의 두번째 값은 sub2
		vp.push_back(p); //벡터의 갱신
	}
	
	//sub2의 난이도를 비교하여 140점을 최대한 많이 더한다.
	for (int i = 0; i < vp.size(); i++) {
		if (cnt == K) { //현재까지 푼 문제의 수가 풀 수 있는 문제수와 같으면
			break; //탈출
		}
		if (vp[i].second <= L) { //두번째 난이도가 역량보다 쉬우면
			cnt++; //푼 문제의 수 증가
			score = score + 140; //획득한 점수의 140점을 더한다.
			st.insert(i); //점수를 더한 문제는 다시 더하지 않도록 번호를 기억한다.
		}
	}

	//sub1의 난이도를 비교하여 100점을 더한다.
	for (int i = 0; i < vp.size(); i++) {
		if (cnt == K) { //현재까지 푼 문제의 수가 풀 수 있는 문제의 수와 같으면
			break; //턀출
		}
		if (vp[i].first <= L) { //sub1의 난이도가 역량보다 쉬우면
			if (st.find(i) != st.end()) { //이미 풀었던 문제이면 
				continue; //무시
			}
			cnt++; //푼 문제의 수 증가
			score = score + 100; //획득한 점수의 100점을 더한다.
		}
	}

	cout << score;
}