[백준_16439번] 치킨치킨치킨

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) 가 주어집니다.

 

[코드]

import java.util.*;

public class BaekJoon_16439 {
	static int n,m,max=0;
	static int[][] chicken;
	static boolean[] visited;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt(); // 회원 수 
		m=sc.nextInt(); // 치킨 종류
		
		chicken=new int[n][m];
		visited=new boolean[m];
		
		for(int i=0;i<n;i++)
			for(int j=0;j<m;j++)
				chicken[i][j]=sc.nextInt();
		
		dfs(0,0);
		System.out.println(max);
	}
	
	static void dfs(int depth,int start) {
		// m 종류의 치킨 중 3개의 치킨이 선택됐다면
		if(depth==3) {
			int sum=0;
			/*
			 * 각 회원마다 선택된 3종류의 치킨 중 가장 선호도가 높은 치킨을 선택하고
			 * 그 누적 합을 구해 최댓값을 갱신한다.
			 */
			for(int i=0;i<n;i++) {
				int num=0;
				for(int j=0;j<m;j++) {
					// 선택된 치킨 중 가장 선호도가 높은 치킨 찾기
					if(visited[j]==true)
						num=Math.max(num, chicken[i][j]);
				}
				sum+=num;
			}
			
			max=Math.max(max, sum);
			return;
		}
		
		// m개의 치킨 중 3개의 치킨을 중복 없이 선택
		for(int i=start;i<m;i++) {
			if(visited[i]==false) {
				visited[i]=true;
				dfs(depth+1,i+1);
				visited[i]=false;
			}
		}
	}
}

 

[고찰]

 이번 문제는 m개의 치킨 중 3종류를 선택할 수 있는 모든 경우를 백트래킹을 사용하여 완전탐색하는 문제였다. 처음에 풀다가 한 가지 실수를 범했는데 3종류의 치킨을 선택한 후 각 회원마다 3종류의 치킨 중 가장 선호도가 높은 치킨을 선택하는 과정을 빠뜨려 오답 처리를 받았다. 회원 수가 4명이상이 넘어가면 한 사람은 다른 사람이 선택한 치킨을 중복으로 선택해야하기 때문에 이 과정을 반드시 포함시켜주어야 한다.