4-A 19942 다이어트 사전순정렬 질문있습니다

작성한 질문수 15

0

안녕하세요 선용님 ㅎㅎ

문제는 해결하였는데 큰돌님께서 강의해주신부분에서 사전순정렬이 std::sort에서 map일경우 ret_v가 key순으로 오름차순 정렬될텐데 해당 정렬이 key는 동일할텐데 어떻게 오름차순으로 사전순정렬되는지가 이해가 잘 되지않습니다

>>

map<int, vector<vector<int>>> ret_v;

>> int형 key는 사전순 정렬이 자동으로 됩니다.

value는 정렬이 되지 않죠.

그래서 이렇게 정렬을 했습니다.

        sort(ret_v[ret].begin(), ret_v[ret].end());

선용님 코드리뷰

깔끔하고 좋네요. 구조체, 초기값, 로직 모두 깔끔합니다. 긴 부분이 있지만 그건 그렇게 나쁜 코드는 아닙니다.

#pragma once
#include <bits/stdc++.h>

int n;
int mp, mf, ms, mv;
struct Food
{
	int p;
	int f;
	int s;
	int v;
	int c;
	Food(int _p, int _f, int _s, int _v, int _c)
	{
		p = _p;
		f = _f;
		s = _s;
		v = _v;
		c = _c;
	}
};
std::vector<Food> Foods;
int min = 999999999;
int min_price = 999999999;
int CheckOrder(int cur, int min)
{
    // 다 구현해서 좀 길지만 괜찮습니다. GOOD
	std::vector<int> curs;
	std::vector<int> mins;
	for (int i = 0; i < n; i++)
	{
		if (cur & (1 << i))
		{
			curs.push_back(i + 1);
		}
	}
	for (int i = 0; i < n; i++)
	{
		if (min & (1 << i))
		{
			mins.push_back(i + 1);
		}
	}
	int minsize = curs.size() <= mins.size() ? curs.size() : mins.size();
	for (int i = 0; i < minsize; i++)
	{
		if (mins[i] == curs[i])
			continue;
		else if (mins[i] > curs[i])
			return cur;
		else
			return min;
	}
	if (curs.size() < mins.size())
		return cur;
	return min;
}
void Check(int cur)
{
    // 좋습니다. GOOD
	int _p = 0, _f = 0, _s = 0, _v = 0, _c = 0;
	for (int i = 0; i < n; i++)
	{
		if (cur & (1 << i))
		{
			_p += Foods[i].p;
			_f += Foods[i].f;
			_s += Foods[i].s;
			_v += Foods[i].v;
			_c += Foods[i].c;
		}
	}
	if (_p >= mp && _f >= mf && _s >= ms && _v >= mv && _c <= min_price)
	{
		
		if (_c < min_price)
		{
			min_price = _c;
			min = cur;
		}
		else
		{
			min_price = _c;
			min = CheckOrder(cur, min);
		}
	}
}

int main(void)
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	std::cin >> n;
	std::cin >> mp >> mf >> ms >> mv;
	for (int i = 0; i < n; i++)
	{
		int p, f, s, v, c;
		std::cin >> p >> f >> s >> v >> c;
		Foods.push_back(Food(p, f, s, v, c));
	}
	for (int i = (1 << n) - 1; i >= 1; i--)
	{
		Check(i);
	}
    // min값 초기값 항상 체크해서 해주세요 : GOOD
	if (min_price > 99999999)
	{
		std::cout << -1;
		return 0;
	}
	std::cout << min_price << '\n';
	for (int i = 0; i < n; i++)
	{
		if (min & (1 << i))
		{
			std::cout << i + 1 << " ";
		}
	}
	return 0;
}

감사합니다.