백준 16439 치킨치킨치킨 c++ (조합)

문제 출처 : https://www.acmicpc.net/problem/16439

16439번: 치킨치킨치킨

문제

N명의 고리 회원들은 치킨을 주문하고자 합니다.

치킨은 총 M가지 종류가 있고 회원마다 특정 치킨의 선호도가 있습니다. 한 사람의 만족도는 시킨 치킨 중에서 선호도가 가장 큰 값으로 결정됩니다. 진수는 회원들의 만족도의 합이 최대가 되도록 치킨을 주문하고자 합니다.

시키는 치킨의 종류가 많아질수록 치킨을 튀기는 데에 걸리는 시간도 길어지기 때문에 최대 세 가지 종류의 치킨만 시키고자 합니다.

진수를 도와 가능한 만족도의 합의 최댓값을 구해주세요.

입력

첫 번째 줄에 고리 회원의 수 N (1 ≤ N ≤ 30) 과 치킨 종류의 수 M (3 ≤ M ≤ 30) 이 주어집니다.

두 번째 줄부터 N개의 줄에 각 회원의 치킨 선호도가 주어집니다.

i+1번째 줄에는 i번째 회원의 선호도 ai,1, ai,2, ..., ai,M (1 ≤ ai,j ≤ 9) 가 주어집니다.

출력

첫 번째 줄에 고리 회원들의 만족도의 합의 최댓값을 출력합니다.

알고리즘 분류

• 브루트포스 알고리즘

풀이

조합을 이용한 완전 탐색 문제이다.

우선 문제 이해가 잘 안됐었는데,

2번 예제를 풀어 보자.

우선 주어진 입력의 해석은 다음과 같다.

0번 사람의 6가지 치킨 종류에 대한 선호도 1 2 3 4 5 6

1번 사람의 6가지 치킨 종류에 대한 선호도 6 5 4 3 2 1

2번 사람의 6가지 치킨 종류에 대한 선호도 3 2 7 9 2 5

3번 사람의 6가지 치킨 종류에 대한 선호도 4 5 6 3 2 1

이를 2차원 배열로 나타내면 arr[i][j] = i번 사람의 j번 치킨에 대한 선호도이다.

사람은 4명이 있고 시키는 치킨은 총 세 마리다.

0부터 5번 까지 치킨의 종류에서 3 종류의 치킨을 골라 시키고, 0번부터 3번까지 사람 모두,

3 종류의 치킨 중 가장 선호하는 치킨의 값의 합을 구하면 된다.

 

만약 1 3 5 치킨을 고르고, 0 1 2 치킨을 골랐다고 하자.

arr[0][1,3,5] = 2, 4, 6 

arr[1][1,3,5] = 5, 3, 1

arr[2][1,3,5] = 2, 9, 5

arr[3][1,3,5] = 5, 3, 1

1 3 5 치킨을 골랐을 때 네 명의 최대 선호도 합은 25이다.

 

arr[0][0,1,2] = 1, 2, 3

arr[1][0,1,2] = 6, 5, 4

arr[2][0,1,2] = 3, 2, 7

arr[3][0,1,2] = 4, 5, 6

0 1 2 치킨을 골랐을 때 네 명의 최대 선호도 합은 18이다.

 

만족도 합의 최댓값을 구해야 하기 때문에 위의 치킨을 고르는 조합을 비교하여 큰 값인 25가 최대 선호도로 갱신되는 것이다.

 

즉 NCM 조합을 구하고, M 개의 치킨이 추려질 때마다, 최대 선호도 값을 비교하면 된다.

나는 이제 어제 먹고 남은 황금 올리브 치킨을 먹을 것이다.

코드

#include <iostream>
#include <algorithm>
using namespace std;
int n, m;
int arr[30][30];
int pick[3];
int result;
void combination(int idx, int cnt) {
	if (cnt != -1) {
		pick[cnt] = idx;
	}
	if (cnt == 2) {
		int sum = 0;
		for (int i = 0; i < n; i++) {
			int score = 0;
			for (int j = 0; j < 3; j++) {
				score = max(arr[i][pick[j]], score);
			}
			sum += score;
		}
		result = max(sum, result);
		return;
	}
	for (int i = idx; i < m; i++) {
		combination(i + 1, cnt + 1);
	}
}

int main() {
	ios::sync_with_stdio(false);
	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];
		}
	}
	combination(-1, -1);
	cout << result;
	return 0;
}