알고리즘 공부 (2024_11_12)

아휴...알고리즘 공부가 쉽지가 않네...

이거 뭐 푼 문제가 있어야 올리지...마음이 꺾인다....

 

요즘 안올린건 문제를 안푼게 아니고 거진 2~3시간을 한두문제만 풀어서 그렇다...

그래도 배낀거라도 올려야 할거 같아서 글 씁니다..

 

백준 2258 : 정육점

지정한 무게 아래가 아니고 가격 아래를 모두 고려해야 하는 문제.

여러개의 같은 무게가 있을 수 있고, 여러개의 같은 가격이 있을 수도 있기 때문에 이 모든 경우를 고려해야 하는 문제.

#include <stdio.h>
#include <algorithm>
#include <queue>
#include <vector>
#include <iostream>
#include <fstream>
#include <stack>
#include <math.h>
#include <string>
#include <climits>

struct Info
{
    long long Kg;
    long long Price;

    Info(long long a, long long b) : Kg(a), Price(b) {};

    const bool operator<(Info& other) const
    {
        if (other.Price == Price)
        {
            return other.Kg < Kg;
        }
        else
        {
            return other.Price > Price;
        }
    }
};

using namespace std;
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    int N, M;
    long long A, B;
    cin >> N >> M;

    vector<Info> NV;

    for (int i = 0; i < N; i++)
    {
        cin >> A >> B;
        NV.push_back(Info(A,B));

    }

    sort(NV.begin(), NV.end());
	int KgSum = 0;
	int PriceSum = 0;
	int before = -1;
	for (int i = 0; i < NV.size(); i++)
	{
		if (KgSum < M)
		{
			if (before == NV[i].Price)
			{
				PriceSum += NV[i].Price;
			}
			else
			{
				before = PriceSum = NV[i].Price;
			}
		}
		else
		{
			if ((before != NV[i].Price) && (PriceSum >= NV[i].Price))
			{
				before = PriceSum = NV[i].Price;
			}
		}

		KgSum += NV[i].Kg;
	}

	if (KgSum < M)
		cout << -1 << endl;
	else
		cout << PriceSum << endl;

	return 0;
}

 

 

---

 

 

백준 12018 : Yonsei TOTO

 

#include <stdio.h>
#include <algorithm>
#include <queue>
#include <vector>
#include <iostream>
#include <fstream>
#include <stack>
#include <math.h>
#include <string>
#include <climits>

using namespace std;
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    int N, M;
    cin >> N >> M;

    vector<int> NV;
    int Answer = 0;
    int Count = 0;

    for (int i = 0; i < N; i++)
    {
        vector<int> PV;
        int P, L;
        cin >> P >> L;

        for (int j = 0; j < P; j++)
        {
            int k;
            cin >> k;
            PV.push_back(k);
        }

        if (L > P)
        {
            NV.push_back(1);
        }
        else
        {
            sort(PV.begin(), PV.end(), greater<int>());

            int opt = PV[L - 1];
            NV.push_back(opt);
        }

    }

    sort(NV.begin(), NV.end());
    for (int i = 0; i < NV.size(); i++)
    {
        Count += NV[i];

        if (Count <= M) 
        {
            Answer++;
        }
        else
        {
            break;
        }
    }

    cout << Answer;
	return 0;
}