[SWEA 2115] 벌꿀채취

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V4A46AdIDFAWu 

SW Expert Academy

 

---

[1회차] 10월 2일날 풀었어서 코드만 첨부

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
 
public class Solution {
    static int N, M, C, ans, max;
    static int map[][], honeys[];
    static boolean isVisited[];
    static List<Honey> list;
 
    static class Honey{
        int x, s_y, e_y, cnt, total;
        public Honey(int cnt, int total){
            this.cnt = cnt;
            this.total = total;
        }
        public Honey(int x, int s_y, int e_y, int total){
            this.x = x;
            this.s_y = s_y;
            this.e_y = e_y;
            this.total = total;
        }
    }
    public static void main(String args[]) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(in.readLine());
 
        for (int test_case = 1; test_case <= T; test_case++) {
            StringTokenizer st = new StringTokenizer(in.readLine());
 
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            C = Integer.parseInt(st.nextToken());
 
            map = new int[N][N];
 
            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(in.readLine());
                for (int j = 0; j < N; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                }
            }
            ans = Integer.MIN_VALUE;
            getHoneys();
            sb.append("#" + test_case + " " + ans + "\n");
        }
        System.out.println(sb);
    }
 
    private static void getHoneys() {
        list = new ArrayList<>();
 
        for (int i = 0; i < N; i++) {
            for (int j = 0; j <= N - M; j++) {
                honeys = new int[M];
                for (int k = 0; k < M; k++) {
                    honeys[k] = map[i][j+k];
                }
                isVisited = new boolean[M];
                max = Integer.MIN_VALUE;
                findMaxHoney(0);
                list.add(new Honey(i, j, j + M, max));
            }
        }
 
        isVisited = new boolean[list.size()];
        Honey[] order = new Honey[2];
        combi(0, 0, order);
    }
 
    private static void combi(int depth, int start, Honey[] order){
        if(depth == 2){
            if(order[0].x == order[1].x && order[0].e_y > order[1].s_y){
                return;
            }
            if(order[0].total + order[1].total < ans) return;
            ans = Math.max(ans, order[0].total + order[1].total);
            return;
        }
 
        for (int i = start, size = list.size(); i < size; i++) {
            if(!isVisited[i]){
                isVisited[i] = true;
                order[depth] = list.get(i);
                combi(depth+1, i+1, order);
                isVisited[i] = false;
            }
        }
    }
 
    private static void findMaxHoney(int depth) {
        if(depth == M) {
            Honey h = new Honey( 0, 0);
            for (int i = 0; i < M; i++) {
                if(isVisited[i]){
                    h.cnt += honeys[i];
                    h.total += honeys[i] * honeys[i];
                }
                if(h.cnt > C){
                    h.total = 0;
                    return;
                }
            }
            max = Math.max(h.total, max);
            return;
        }
 
        // arr에 있는 값들 중 합이 C를 넘기지 않으면서 제곱의 값의 합이 가장 큰 것을 찾아야 함 -> 부분집합?
        isVisited[depth] = true;
        findMaxHoney(depth + 1);
        isVisited[depth] = false;
        findMaxHoney(depth + 1);
    }
}

 

 

아마 이 문제 푸는데 시간이 조금 오래 걸렸었던 것 같다. 뭔가 하나 조건에 안 맞았던 것 같은데...

---

[2회차] 10월 25일 

 

문제 접근 방법 (사용 자료구조, 알고리즘)

1. 입력 => T(테스트 케이스 개수), N, M, C, 벌꿀장 
2. M개의 벌꿀통에서 채취할 수 있는, C를 넘지 않는 최대 벌꿀양의 수익량을 계산 → 부분집합
이 때, 무조건 M개를 채취해야하는 건 아니고 M=3, C=10일 경우 [7, 2, 9] 에서는 9만 채취를 하는게 가장 벌꿀 수익량이 많다.
나는 이 조건을 자세히 안 봐서 결국 다시 돌아와서 추가했다. -> 부분집합으로 완전탐색 시전 -> 뭔가 더 간단한 방법이 있을 것 같다...
3. 채취한 경우의 수 중에서 2개 선택해서 범위에 겹치는지 판별, 겹치지 않는다면 ans를 최대값으로 갱신 → 조합
나는 벌꿀을 채취하는 사람이 특정 2명이 아니고 A명도 될 수 있다고 확장해서 생각해서 boolean 2차원 배열로 판별해주었다.

 

 

 

문제를 푼 시간 (문제 해석 + 문제 접근 + 코드 구현)

문제 해석	문제 로직 설계	코드 구현
3분	10분	40분

 

 

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;
 
public class Solution {
    static int N, M, C, map[][], ans, selected[], total;
    static List<Honey> honeys;
    static boolean[] visited;
     
    static class Honey{
        int x, start, end, amount;
 
        public Honey(int x, int start, int end, int amount) {
            this.x = x;
            this.start = start;
            this.end = end;
            this.amount = amount;
        }
    }
 
    public static void main(String[] args) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(in.readLine());
         
        for (int test_case = 1; test_case <= T; test_case++) {
            // 1. 입력
            StringTokenizer st = new StringTokenizer(in.readLine());
             
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            C = Integer.parseInt(st.nextToken());
             
            map = new int[N][N];
            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(in.readLine());
                for (int j = 0; j < N; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                }
            }
             
            // 2. M 개 채취 배열생성 -> 채취량이 C를 넘으면 안 되면서 && 최댓값을 찾아 주어야 함 
            honeys = new ArrayList<>();
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N - M + 1; j++) {
                    // 여기서도 조합을 쓰는게 맞을까..?
                    int[] catchHoneys = new int[M];
                    for (int k = 0; k < M; k++) {
                        catchHoneys[k] = map[i][j + k];
                    }
                    total = 0;
                    visited = new boolean[M];
                    getHoneyMax(catchHoneys, 0);
                    honeys.add(new Honey(i, j, j + M - 1, total));
                }
            }
             
            // 3. 채취한 경우의 수 중 2개 선택, 조합
            visited = new boolean[honeys.size()];
            selected = new int[2];
            ans = Integer.MIN_VALUE;
            combi(0, 0);
             
            sb.append("#" + test_case + " " + ans + "\n");
        }
        System.out.println(sb);
    }
 
    private static void getHoneyMax(int[] catchHoneys, int depth) {
        if(depth == M) {
            int[] amount = new int[2];
            for (int i = 0; i < M; i++) {
                if(visited[i]) {
                    amount[0] += catchHoneys[i];
                    if(amount[0] > C) return;
                    amount[1] += Math.pow(catchHoneys[i], 2);
                }
            }
            total = Math.max(total, amount[1]);
            return;
        }
         
        visited[depth] = true;
        getHoneyMax(catchHoneys, depth+1);
         
        visited[depth] = false;
        getHoneyMax(catchHoneys, depth+1);
    }
 
    private static void combi(int depth, int start) {
        if(depth == 2) {
            boolean[][] check = new boolean[N][N];
            int amount = 0;
             
            // 같은 위치거나 겹치면은 안됨 -> 그렇지 않으면 정답 갱신 
            for (int i = 0; i < 2; i++) {
                Honey h = honeys.get(selected[i]);
                for (int j = h.start; j <= h.end; j++) {
                    if(check[h.x][j]) return;
                    check[h.x][j] = true;
                }
                amount += h.amount;
            }
             
            ans = Math.max(ans, amount);
            return;
        }
         
        for (int i = start; i < honeys.size(); i++) {
            if(!visited[i]) {
                visited[i] = true;
                selected[depth] = i;
                combi(depth+1, i+1);
                visited[i] = false;
            }
        }
    }
 
}

 

 

 

 

메모리 & 시간

메모리 ⬆, 시간 2초 ⬆

아마 판별 과정에서 boolean 배열을 사용해서 더 커진 것 같다

아마 채취 과정에서 좀 더 효율적으로 생각할 수 있는 방법이 있을 것 같다

 

 

 

 

체감 난이도

中