백준 16439번 - 치킨치킨치킨

황제연·2024년 10월 31일

16439 백준 백트래킹 완전탐색 자바 치킨치킨치킨

알고리즘

목록 보기

120/169

문제 탐색하기

입력 자료 정리

입력값 n은 회원의 수, m은 치킨의 종류이다.
이후 들어오는 n번당 m번의 입력은 각 회원의 치킨 종류별 선호도이다.

해결 방법 추론

너무 많이 선택하는 것을 막기 위해 선택하는 종류는 3가지로 제한하였다
또한 합산도 아니며, 선택된 치킨 종류 중 각 회원이 가장 선호하는 치킨을 선택한다.
따라서 출력 정답 변수는 int형 범위일 것이고,
n과 m이 30이므로 완전탐색으로 해결 가능하다
사실 이 문제는 백트래킹으로도 가능하다.
하지만 이전에 해당 방식으로 풀었고 단순 포문으로 해결하는 완전탐색 실력을 키우기 위해
이번에는 단순 포문으로 해결할 것이다
이 문제를 단순 포문으로 해결하려면 5중 포문으로 해결해야한다
3가지를 중복없이 뽑는 경우와, n명의 사람들을 순회하면서 m개의 치킨 종류를 살펴보고
이중에서 선택된 치킨들에 대해 최댓값을 구해야하기 때문이다
따라서 앞선 3중 포문에서는 중복없이 뽑기 위해 이전 포문의 인덱스에 +1한 인덱스로 탐색한다
n과 m 탐색을 할 때는 변수를 하나씩 두어서 최대값을 각각 구하고
앞선 3중 포문에서 선택된 값으로 했을 때의 합산을 구한 뒤,
최댓값을 구하기 위해 비교하는 과정을 거친다면 해결할 수 있을 것이다.

시간복잡도 계산

시간복잡도는 5중 포문이며, m을 4번, n을 한번 순회하므로
O(n x m^4)이 될 것이다.
n과 m의 최댓값은 30이며, 계산했을 때 대략 2400만 정도이므로
시간제한안에 문제를 해결할 수 있다.

코드 설계하기

입력값 상태 관리

입력값은 int형 타입의 2차원 배열로 관리한다
n과 m은 변수로 관리하며, 각각 int형 타입의 2차원 배열의 크기를 결정한다
정답 출력을 위해 ans 변수를 0으로 초기화한다

구현코드 설계

앞서 추론한 방식대로 5중 포문으로 설계한다
i는 0부터, j는 i+1부터 k는 j+1부터 순회해서 중복 선택되지 않도록 한다
이어서 선택된 i,j,k가 치킨의 종류라고 했을 때, 각 사람별로 최댓값을 구해야한다
n명의 사람을 m개의 치킨 선호도를 파악하며 답을 찾도록 순회한다
이때 m개의 치킨 선호도를 파악하며 최댓값을 찾기 위해 max 변수를 0으로 초기화한다
i, j, k가 o와 같은 경우에는 max와 비교하여 최댓값을 구한다
m개의 치킨 종류에서 선호도 파악이 끝난 경우,
현재 선택된 치킨 종류에서 선호도 합산을 담을 sum변수에 max를 더해준다
n명의 사람을 모두 확인한 후에는 ans에 sum값과 비교하여 최댓값을 넣어준다.

출력값 설계

완성된 ans를 출력하면 정답이 된다.

정답 코드

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


public class Main {



    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int[][] arr = new int[n][m];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        int ans = 0;

        for (int i = 0; i < m; i++) {
            for (int j = i+1; j < m; j++) {
                for (int k = j+1; k < m; k++) {
                    int sum = 0;
                    for (int l = 0; l < n; l++) {
                        int max = 0;
                        for (int o = 0; o < m; o++) {
                            if(i == o  || j == o || k == o){
                                max = Math.max(arr[l][o], max);
                            }
                        }
                        sum += max;
                    }
                    ans = Math.max(ans, sum);
                }
            }
        }


        bw.write(ans+"");

        br.close();
        bw.close();
    }
}