[백준] 16439_치킨치킨치킨 🍗 (JAVA)

1. 문제

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

16439번: 치킨치킨치킨

---

 

2. 문제 이해

처음에 문제 이해가 안됐었다ㅠㅠ 진짜... 난이도 실버4인데...

고민 끝에 이해한 내용이다. → 한 사람의 만족도는 시킨 치킨 중에서 선호도가 가장 큰 값으로 결정된다.

치킨 튀기는 데에 시간이 오래걸려서 최대 3가지 종류의 치킨만 시킴

 

예를 들어

3 5 -> 세사람이 5종류의 치킨을 시킨다 ( a b c d e)

1 2 3 4 5

5 4 3 2 1

1 2 3 2 1 -> 이 애들은 각각의 치킨의 선호도이다.

 

만족도는 고른 치킨중에서 선호도가 가장 큰 값을 결정하고, 만족도의 합이 최대를 구하는 것 (핵심)

 

 

3. 풀이 방법

1. N개의 치킨종류 중에서 3개의 치킨종류를 뽑을 것 (치킨을 뽑을 때 a,b,c/ b,c,a 처럼 순서가 필요가 없으니깐 조합)

2. 뽑은 치킨의 선호도 배열에서 제일 큰 값을 구해주기 (뽑은 3개의 치킨 각각 따로)

3. 각각 뽑은 선호도를 더해줘서 Max값이랑 비교해주고

4. nCr이 다 돌면 Max 값 뽑아주기!

 

순열 조합 이해

• 순열은 1명은 회장, 1명은 부회장 뽑는 것 (순서 존재) 서로 다른 n개에서 r를 순서 있게 뽑는 것
• 조합은 2명의 대표를 뽑는 것(순서 존재 x) 서로 다른 N개에서 R개를 순서 없이 뽑는 것

 

 

 

4. 코드

package net.acmicpc.solution;

import java.util.*;
import java.io.*;

public class Solution_16439_치킨치킨치킨 {

	static int N, M; // 회원수, 치킨 종류의 수
	static int[][] preference; // 선호도
	static int max; // 만족도 최대값 (즉 정답)
	static int[][] manjok; // 매번 바뀔 선호도 (조합에 쓰일 애)

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		preference = new int[N][M];

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				preference[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		manjok = new int[N][3];

		nCr(0, 0);
		System.out.println(max);

	}

	private static void nCr(int cnt, int start) {
		if (cnt == 3) {
//			for (int i = 0; i < N; i++) {
//				for (int j = 0; j < 3; j++) {
//					System.out.print(manjok[i][j] + " ");
//				}
//				System.out.println();
//			}
//			System.out.println("=======================");
			int sum = 0;
			for (int i = 0; i < N; i++) {
				int m = Integer.MIN_VALUE;
				for (int j = 0; j < 3; j++) { 
					m = Math.max(m, manjok[i][j]);
				}
				sum += m;
			}
			max = Math.max(max, sum);

			return;
		}

		for (int i = start; i < M; i++) {
			for (int k = 0; k < N; k++) {
				manjok[k][cnt] = preference[k][i];
			}
			nCr(cnt + 1, i + 1);
		}

	}
}

 

피드백은 언제나 환영입니다 :) 🌳