인프런 커뮤니티 질문&답변

안녕하세요 ㅎㅎ

이부분만 바꿔서 제출해보시면 맞게 나옵니다.

#include <bits/stdc++.h>
using namespace std;
const int INF = 987654321;
int n, mp, mf, ms, mv, rp, rf, rs, rv, rc, cost = INF;
int p[16], f[16], s[16], v[16], c[16]; 
map<int, vector<vector<int>>> temp;
vector<int> vec, ret;
int main(){
    cin >> n >> mp >> mf >> ms >> mv;
    for(int i = 1; i <= n; i++){
        cin >> p[i] >> f[i] >> s[i] >> v[i] >> c[i];
    }
    for(int i = 0; i < (1 << n); i++){
        vec.clear();
        rp = 0; rf = 0; rs = 0; rv = 0; rc = 0;
        for(int j = 0; j < n; j++){
            if(i & (1 << j)){
                vec.push_back(j + 1);
            }
        }
        for(int k : vec){
            rp += p[k];
            rf += f[k];
            rs += s[k];
            rv += v[k];
            rc += c[k];
        }
        if(rp < mp || rf < mf || rs < ms || rv < mv) continue;
        if(rc < cost){
            cost = rc;
            ret.clear();
            ret = vec;
			temp[cost].push_back(vec); 
            continue;
        }
        if(rc == cost){ 
			temp[cost].push_back(vec); 
            vec.clear();
        }
    } 
    if(cost == INF) cout << "-1" << '\n';
    else{  
    	sort(temp[cost].begin(), temp[cost].end());
        cout << cost << '\n';
        for(int i : temp[cost][0]) cout << i << " ";
    }
    return 0;
}

즉,

이부분이 틀린 건데요.

        if(rc == cost){
            int length = vec.size() < ret.size() ? vec.size() : ret.size();
            for(int k = 0; k < length; k++){
                if(vec[k] < ret[k]){
                    ret.clear();
                    ret = vec;
                }
            }
        }

이게 왜 틀렸을까요?

저도 이부분은 맞다고 생각하는데..

저도 이해가 안되서

한번 예제를 만들어서 해봤습니다.

#include <bits/stdc++.h>
using namespace std;  
vector<vector<int>> ret;
int max_n = 9; 
/*
vec < ret
1 2 3 4 5 6 7 8 9
1 2 3 4 5 8
vec < ret
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 8
*/
	int cnt = 0;
void f(vector<int> vec, vector<int> ret){ 
    int length = vec.size() < ret.size() ? vec.size() : ret.size(); 
    for(int k = 0; k < length; k++){
        if(vec[k] < ret[k]){  
        	if(vec.size() == ret.size()){
				if(++cnt == 1000) exit(0);
	        	cout << "vec < ret \n";
	        	for(int i : vec) cout << i << ' ';
	        	cout << '\n';
	        	for(int i : ret) cout << i << ' ';
	        	cout << '\n';  
			} 
        	return;
        }
    }  
    
} 
int main(){
	vector<int> v;
	for(int i = 1; i <= max_n; i++){
		v.push_back(i);
	}
	do{ 
		for(int j = 1; j <= max_n; j++){
			vector<int> temp; 
			for(int i = 0; i < j; i++){
				temp.push_back(v[i]);
			}
			sort(temp.begin(), temp.end());
			ret.push_back(temp);
		} 
	}while(next_permutation(v.begin(), v.end()));  
	for(int i = 0; i < ret.size(); i++){
		for(int j = 0; j < i; j++){
			f(ret[i], ret[j]); 
		}
	}
    return 0;
}

자, 이걸 돌려보면요.

vec < ret

1 2 3 4 5 6 7 8 9

1 2 3 4 5 8

vec < ret

1 2 3 4 5 6 7 8 9

1 2 3 4 5 6 8

잘 나옵니다. 로직이 잘됩니다..

1 2 3 4 5 7 8 9

vec < ret

1 2 3 4 5 6 8 9

1 2 3 4 5 7 8 9

vec < ret

1 2 3 4 5 6 8 9

1 2 3 4 5 7 8 9

vec < ret

1 2 3 4 5 6 8 9

1 2 3 4 5 7 8 9

vec < ret

같은 사이즈인지 확인하는 로직을 넣어도 됩니다.

즉, 저부분이 틀린지는 확인을 했으나 왜 틀린지는 저도 잘 모르겠습니다. ㅠㅠ

많이 봤는데... 제 역량 부족이네요.. 일단 넘어가시고 저도 시간 남을 때 한번 더 보겠습니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.