백준 16439. 치킨치킨치킨

치킨치킨치킨

브루트포스 문제

1. 간단 설명

---

N명의 사람이 M개의 치킨중 세가지 치킨을 고른다

이 사람들이 각 치킨에 대한 선호도가 주어지는데

세마리 치킨을 골라서 선호도가 최대가 하도록 하는 문제

한 사람의 만족도는 시킨 치킨 중에서 선호도가 가장 큰 값으로 결정된다

2. 예시

---

3 5
1 2 3 4 5
5 4 3 2 1
1 2 3 2 1

3명의 회원, 5가지 치킨 종류

각 회원의 치킨 선호도가 주어질 때

치킨 3개를 골라 최대 만족도를 구하면

1, 3, 5번 치킨 고른 경우

1번 사람은 5번 치킨 -> 만족도 5
2번 사람은 1번 치킨 -> 만족도 5
3번 사람은 3번 치킨 -> 만족도 3

13이 최대값이다

3. 알고리즘

---

사람은 최대 30명, 치킨은 최대 30종류다

치킨은 세마리를 고르므로 30C3 을 구한다음 이때 각 사람별 만족도를 계산한다

30C3 = 30 * 29 * 28 / 3 * 2 * 1 = 약 4천가지 경우의 수 이므로 완전탐색으로 가능

1. N, M 입력받기
2. 각 사람의 치킨 만족도 입력받기
3. 조합을 이용해 치킨 세마리 고른다
	3-1. 고른 치킨들을 통해 각 사람의 최대 선호도를 계산한다
	3-2. 구한 최대 선호도를 전체 선호도에 합산 후 기록된 값과 비교한다
4. 최대 전체 선호도를 출력 후 종료

필요 변수

• int N, M 최대 30명, 치킨 30마리
• int max_val 전체 선호도의 최대값
• int cost[31][31] 각 사람들의 각 치킨에 대한 선호도

4. 소스코드

---

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N, M;
int max_val = 0;
int cost[31][31];

void Input() {
	// freopen_s(new FILE*, "input.txt", "r", stdin);

	cin >> N >> M;
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < M; x++) {
			cin >> cost[y][x];
		}
	}
}

int main() {
	Input();

	for (int i = 0; i < M; i++) {
		for (int j = i + 1; j < M; j++) {
			for (int k = j + 1; k < M; k++) {
				int cur_val = 0;

				for (int person = 0; person < N; person++) {
					cur_val += max({ cost[person][i], cost[person][j], cost[person][k] });
				}

				max_val = max(max_val, cur_val);
			}
		}
	}

	cout << max_val;

	return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N, M;
int max_val = 0;
int cost[31][31];

void Input() {
	// freopen_s(new FILE*, "input.txt", "r", stdin);

	cin >> N >> M;
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < M; x++) {
			cin >> cost[y][x];
		}
	}
}

int main() {
	Input();

	vector<int> idx;
	for (int i = 0; i < M - 3; i++) {
		idx.push_back(0);
	}
	for (int i = 0; i < 3; i++) {
		idx.push_back(1);
	}

	int de = -1;

	do {
		int cur_val = 0;
		for (int i = 0; i < N; i++) {
			int person_val = 0;
			for (int j = 0; j < M; j++) {
				if (idx[j] == 1 && person_val < cost[i][j]) {
					person_val = cost[i][j];
				}
			}
			cur_val += person_val;
		}
		
		if (cur_val > max_val) {
			max_val = cur_val;
		}

	} while (next_permutation(idx.begin(), idx.end()));

	cout << max_val;

	return 0;
}

next_permutation을 이용해 조합을 생성한 버전

조합의 경우의 수가 적을떄는 명시적인 반복문으로 처리하는게 간단하고 직관적이다