백준 16439. 치킨치킨치킨

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

16439번: 치킨치킨치킨

 

 

 

1. 문제 설명

 

n 명의 유저가 있고, m가지 종류의 치킨이 있으다

3가지 치킨을 선택했을 때 유저들의 만족도의 합이 최대가 되는 경우를 구해라

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

 

 

2. 접근법

 

이 문제는 브루트 포스 알고리즘으로 풀 수 있다

하지만, 단순한 브루트 포스의 경우 시간초과가 뜬다

 

주어진 입력값의 범위는 N (1 ≤ N ≤ 30)과 M (3 ≤ M ≤ 30) 이다

이때, M = 30이라고 했을 때 30가지 종류의 치킨을 선택하는 방식으로 브루트 포스 알고리즘을 구현할 경우

 

최대 시간복잡도는 2^30이다. 이는 10억을 넘어가기 때문에 시간 제한에 걸린다(주어진 시간 제한 1초)

 

이를 효율적으로 구상해야한다

즉, 불필요한 경우에 대해서는 탐색하지 않아야한다

 

문제에서는 최대 3가지 종류의 치킨을 선택한다고 가정했기 때문에 3가지 넘게 선택하는 경우는 의미가 없다

따라서, 3가지 종류의 치킨을 이미 선택한 경우는 계산하고 재귀호출을 멈춘다

 

즉, 종료조건이 크게 두 가지가 있는 것이다

1. 총 m 가지 치킨을 다 고려한 경우(선택할지 말지)

2. 3 가지 종류의 치킨을 선택한 경우

 

이렇게 2번째 종료 조건을 통해 의미없는 탐색을 하지 않는 것을 가지치기라 하는데, 이는 브루트 포스 알고리즘을 최적화 할 수 있다

 

또한, 다음 순열을 활용하는 풀이도 있다

일단, 0, 1로 이루어진 크기가 m인 배열을 만든다. 이때 3개는 1로 정해놓는다

여기서 0은 선택안함, 1은 선택함을 의미한다

 

예를 들어서, m = 5일 때 [00111]을 시작으로 [11100]까지 만들 수 있는 모든 수열을 만든다

해당 수열의 의미는 몇 번째 치킨을 선택했냐를 의미한다

 

 

3. 설계

 

1. 입력값 받고 세팅

- int n, m, ans

- int[][] users

- static void go(int idx, ArrayList<Integer> seleted) : 선택관점으로 돌리는 브루트 포스 알고리즘을  재귀적으로 구현

- static int calc(ArrayList<Integer> selected) : 만족도 합 계산

 

2. 브루트포스 재귀 호출로 진행

 

3. 결과값 출력하기

 

4. 코드

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



public class Main {

    static int n, m, ans;
    static int[][] users;
    static void go(int idx, int cnt, ArrayList<Integer> selected) {
    	// if i selected 3 chickens then stop recursive call
        if (cnt == 3) {
            int tmp = calc(selected);
            if (ans < tmp) ans = tmp;
            return;
        }
        
        // when i consider all chicken, stop recursive call
        if (idx == m) return;

        // selected 
        selected.add(idx);
        go(idx+1, cnt+1, selected);

		// not selected
        selected.remove(selected.size()-1);
        go(idx+1, cnt, selected);

    }


    static int calc(ArrayList<Integer> selected) {
        int ans = 0;

        for (int i=0; i< users.length; i++) {
            int max = 0;
            for (int j : selected) {
                if (max < users[i][j]) max = users[i][j];
            }

            ans += max;
        }

        return ans;
    }

    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());

        users = new int[n][m];
        for (int i=0; i<n; i++) {
            String[] line = br.readLine().split(" ");
            for (int j=0; j<m; j++) {
                users[i][j] = Integer.parseInt(line[j]);
            }
        }

        go(0, 0, new ArrayList<>());
        System.out.println(ans);

    }
}

 

 

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



public class Main {

    static boolean next_permutation(int[] a) {
        int i = a.length-1;
        while (i > 0 && a[i-1] >= a[i]) {
            i -= 1;
        }

        if (i <= 0) {
            return false;
        }

        int j = a.length-1;
        while (a[j] <= a[i-1]) {
            j -= 1;
        }

        int temp = a[i-1];
        a[i-1] = a[j];
        a[j] = temp;

        j = a.length-1;
        while (i < j) {
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
            i += 1;
            j -= 1;
        }
        return true;
    }


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

        int[][] users = new int[n][m];
        for (int i=0; i<n; i++) {
            String[] line = br.readLine().split(" ");
            for (int j=0; j<m; j++) {
                users[i][j] = Integer.parseInt(line[j]);
            }
        }

        int[] d = new int[m];
        for (int i=0; i<3; i++) {
            d[i] = 1;
        }

        Arrays.sort(d);
        int ans = -1;
        do {
            int tmp = 0;
            for (int i=0; i<n; i++) {
                int max = 0;
                for (int j=0; j<m; j++) {
                    if (d[j] == 0) continue;

                    if (max < users[i][j]) max = users[i][j];
                }
                tmp += max;
            }

            if (ans < tmp) ans = tmp;
        } while (next_permutation(d));
        System.out.println(ans);

    }
}