알고리즘 재활 4일차 - 백준 2805, 15686번

재활하자 재활

빨리 골드문제 더 풀어야하는데,,

 

나무 자르기

 

상근 교수님.. 잘 계시죠..?

 

 

나무의 h 높이 이상 부분을 자른 부분을 상근이가 갖게되는데,

이 자르는 높이의 최대값을 구해보는게 문제이다.

 

대충 나무가 이렇게 가지각색의 길이로 주어진다면 내가 자른 윗부분들의 합이 M이상이어야 한다.

이분 탐색으로 저 높이를 찾아보자.

 

먼저 이분탐색을 low와 hight 또는 left right 등 최소와 최대를 두어주고, 그 가운데 mid 값을 조정하여

값을 찾는 알고리즘이다.

우리가 숫자 up & down 게임을 할때 1~100이라면 50부터 불러서 줄이는것과 같은 로직이다.

만약 4가 정답이라면 1~100까지 하나하나 물어보는게 아닌

100 ▶ 50 ▶ 25 ▶ 12 ▶ 6 ▶ 3 ▶ 4 이런식으로 7번만에 빠르게 찾아낼 수 있다.

 

시간 복잡도는 (N) 에서 (logN)이 된다. 대부분의 이분탐색 활용문제는 시간때문이다.

 

로직 흐름

0과 나무 중 가장 높은 값을 더해 /2로 나누어 중간을 찾는다. ( 범위 0 ~ 최대값 )

해당 중간값으로 잘라 나무의 합을 구한다.

자른 나무의 값이 M보다 크다면 0 ~ 최대값 에서 mid+1 ~ 최대값으로 범위를 바꿔준다.

만약 나무가 부족하다면 0 ~ Mid - 1으로 범위를 바꿔 탐색한다.

예시

만약 초기 min가 0, max가 10일때 mid는 5이다.

따라서 5의 높이로 나무들을 잘라준다.

자른 나무의 합이 요구사항보다 크다면 길이를 5보다 높혀도 되므로,

mid + 1 ~ 10인 6 ~ 10로 범위를 정해 mid 를 8로 높혀준다.

자른 나무의 합이 요구사항보다 적다면 길이를 5보다 줄여야 하므로,
0 ~ mid -1 인 0 ~ 4로 범위를 정해 mid를 2로 낮춘다.

 

import java.io.*;
import java.util.*;
 
public class Main { // S2 나무 자르기
 
    static StringBuilder sb = new StringBuilder();
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
 
        // input
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int answer = 0;
        int [] trees = new int [N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            trees[i] = Integer.parseInt(st.nextToken());
        }
 
        //logic
        int low = 0;
        int high = Arrays.stream(trees).max().getAsInt();
 
        while (low <= high) {
            // Mid가 곧 우리가 찾는 숫자를 찾는 과정.
            int mid = (low + high) / 2;
            long sum = 0; // 10억 까지므로 long
 
            // 자른 나무 합 더해주기
            for (int tree : trees) {
                if (tree > mid) {
                    sum += tree - mid;
                }
            }
            
            // 만약 나무를 덜 잘라도 되는 경우
            if (sum >= M) {
                answer = mid; // mid 값 저장
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
 
        System.out.println(answer);
    }
}

---

치킨 배달

문제 이해가 잘 안갔었다.

정리해보면 가장 효율적인 치킨집과 집사이의 거리를 치킨거리라고 정의한다.

계산방식은 |r1-r2| + |c1-c2| 이며, M개의 치킨집으로 치킨거리의 최소값을 구하는 문제다.

 

구현문제이다 보니 간단하게 작성을 하고 시작했다.

 

1. 먼저 반복을 통해 모든 경우의 수를 따져 M의 개수만큼 가게 지우기
2. 남은 가게 좌표 정리
3. 집이랑 가게 좌표 거리 합
4. 최소값 출력

이렇게 풀었을때 예제는 해결되었으나 가지치기를 안해서 시간초과가 나고 말았다.

불필요한 0의 공간도 탐색을 했기 때문이다.

따라서 집과, 치킨집의 좌표를 리스트에 넣어 보관해주고, 그 좌표들로만 서로 탐색하게 해서 해결할 수 있었다.

 

뻬~

 

import java.io.*;
import java.util.*;
 
public class Main { // G5 나무 자르기
    static int[][] map;
    static boolean[] chk;
    static int N, M, answer;
    static List<int[]> bbq;
    static List<int[]> home;
    static StringBuilder sb = new StringBuilder();
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        // input
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        answer = Integer.MAX_VALUE;
        map = new int[N][N];
 
        bbq = new ArrayList<>();
        home = new ArrayList<>();
 
 
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                // 치킨집과 집의 좌표를 입력단계에서 저장
                if (map[i][j] == 2) {
                    bbq.add(new int[]{i, j});
                }else if(map[i][j] == 1){
                    home.add(new int[]{i, j});
                }
            }
        }
        // boolean으로 M개의 치킨집 고려
        chk = new boolean[bbq.size()];
        dfs(0, 0);
        System.out.println(answer);
    }
 
    // M개의 치킨집만 남기기 -> 모든 경우의 수
    public static void dfs(int start, int cnt) {
        if (cnt == M) {
            int totalDistance = getChickenLength();
            answer = Math.min(answer, totalDistance);
            return;
        }
 
        for (int i = start; i < bbq.size(); i++) {
            chk[i] = true;
            dfs(i + 1, cnt + 1);
            chk[i] = false;
        }
    }
 
    private static int getChickenLength() {
        int totalDistance = 0;
        for (int[] house : home) {
            int minDistance = Integer.MAX_VALUE;
            for (int i = 0; i < bbq.size(); i++) {
                if (chk[i]) {
                    int[] chicken = bbq.get(i);
                    //좌표 계산
                    int distance = Math.abs(house[0] - chicken[0]) + Math.abs(house[1] - chicken[1]);
                    minDistance = Math.min(minDistance, distance);
                }
            }
            totalDistance += minDistance;
        }
        return totalDistance;
    }
}