[백준/c++] 16439번: 치킨치킨치킨

 

 

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

16439번: 치킨치킨치킨

 

 

순서대로 정리를 해보자면

1. 치킨 3개 고르기 (backtracking) : vector에 치킨 종류 <int> 넣기

2. N명의 만족도 구하기 : 시킨 치킨 3개 중 각 회원의 선호도가 가장 큰 값

3. N개의 만족도를 sum에 누적 합산시키면 answer 

 

 

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n, m, arr[31][31], ans = 0;
vector<int> chicken;
bool check[31];

void chooseChicken(int cnt, int s){
    if(cnt == 3){
        int sum = 0;
        for(int i=0; i<n; i++){
            int maxv = 0;
            for(int j=0; j<chicken.size(); j++){
                maxv = max(maxv, arr[i][chicken[j]]);
            }
            sum += maxv;
        }
        ans = max(ans, sum);
        return;
    }
    
    for(int i=s; i<m; i++){
        if(!check[i]){
            check[i] = true;
            chicken.push_back(i);
            chooseChicken(cnt+1, i);
            chicken.pop_back();
            check[i] = false;
        }
    }
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for(int i=0; i<n; i++) for(int j=0; j<m; j++) cin >> arr[i][j];
    chooseChicken(0, 0);
    cout << ans << '\n';
    return 0;
}