백준 16439 - 치킨치킨치킨

Java

16439 번 - 치킨치킨치킨

문제

접근 방법

M개의 치킨 종류 수가 있으므로, DFS를 사용하여 3개의 치킨을 뽑고 사람의 선호도의 점수의 합을 구한다.

구한 합의 최대 값이 만족도의 합의 최댓값이다.

3가지의 치킨 종류를 구할 때, 조합을 이용하여 구한다.

코드

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

public class Main {
	static int n, m, result;
	static int[] sel;
	static int[][] user;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk = new StringTokenizer(br.readLine());
    	n = stoi(stk.nextToken());
    	m = stoi(stk.nextToken());

    	user = new int[n][m];

    	for(int i = 0; i < n; i++) {
    		stk = new StringTokenizer(br.readLine());
    		for(int j = 0; j < m; j++) {
    			user[i][j] = stoi(stk.nextToken());
    		}
    	}

    	sel = new int[3];
    	DFS(0,0);

    	System.out.println(result);
    	br.close();
	}

	// 3가지 종류의 치킨을 뽑는다.
	static void DFS(int lv, int st) {
		if(lv == 3) {
			result = Math.max(result, calScore());
			return;
		}

		for(int i = st; i < m; i++) {
			sel[lv] = i;
			DFS(lv + 1, i + 1);
		}
	}

	// 구한 3가지의 치킨 종류를 통하여 점수를 구한다.
	static int calScore() {
		int sum = 0;

		// 회원 1명씩 비교
		for(int i = 0; i < n; i++) {
			int max = 0;
			// 각 회원이 가지고 있는 치킨의 선호도를 비교하여 가장 선호도가 높은 치킨의 점수를 구한다.
			for(int idx : sel) {
				max = Math.max(user[i][idx], max);
			}
			sum += max;
		}

		return sum;
	}

	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

DFS : 조합

개선할 점