99클럽 코테 스터디 6일차 TIL

백준 - 2805번

문제이해

• N개의 나무가 주어지며, 나무들의 높이는 0 <= 높이 <= 10억 이다.
• 최소 M미터의 나무를 가져가기 위해 설정할 수 있는 절단기의 최대 높이(H)를 구하라.

최대값, 나무의 길이 제한, 나무의 높이 제한.

3가지 키워드를 통해 이분탐색 문제인 것을 알 수 있다.

 

풀이

• 이분탐색을 활용하여 특정 높이(H)를 구한다.
• 주어진 나무들의 각 높이에서 특정 높이를 뺀 값을 모두 더한다(totalHeight).
  만약 특정 높이가 더 높다면 연산하지 않는다.
• 계산된 값과 m을 비교하고 범위를 좁혀가며, 결과값을 찾는다.

---

실패1

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    int n = sc.nextInt();
    int m = sc.nextInt();

    int[] trees = new int[n];
    for (int i = 0; i < n; i++) {
        trees[i] = sc.nextInt();
    }

    int left = 0;
    int right= (int) 1e9;
    int result = 0;

    while (left <= right) {
        int mid = (left + right) / 2;

        int totalHeight = 0;
        for (int tree : trees) {
            if (tree > mid) {
                totalHeight += (tree - mid);
            }
        }
        
        if (totalHeight <= m) {
            result = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    System.out.println(result);
    sc.close();
}

totalHeight 와 m을 비교하는 조건에서 문제가 발견됐다.

 

위 코드의 조건식은 최대 m미터의 나무를 가져가기 위해 필요한 절단기의 최대 높이를 구하는 것이다.

문제에서는 '적어도 m미터의 나무를 ~~' 이라 적혀 있고, 이는 '최소 m미터의 나무를 ~~' 과 말과 동일하다.

결국, 최소 m 이상 얻을 수 있는 최대 높이를 찾는 것이므로 조건을 반대로 줘야 한다.

if (totalHeight >= m) {
    result = mid;
    left = mid + 1;
} else {
    right = mid - 1;
}

실패2

int totalHeight = 0;
for (int tree : trees) {
    if (tree > mid) {
        totalHeight += (tree - mid);
    }
}

자른 나무들의 합을 구하는 부분이다.

 

나무의 수가 적고, 높이도 낮다면 문제가 없지만

만약 나무들의 높이가 10억 미터이고, 총 100만개가 있다면 totalHeight에 오버플로우가 발생한다.

totalHeight를 int 자료형 대신 long으로 변경하여 해결했다.

최종

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    int n = sc.nextInt(); // 나무의 수
    int m = sc.nextInt(); // 필요한 나무 길이

    int[] trees = new int[n];
    for (int i = 0; i < n; i++) {
        trees[i] = sc.nextInt(); // 주어진 나무들의 높이
    }

    int left = 0;
    int right= (int) 1e9;
    int result = 0;

    while (left <= right) {
        int mid = (left + right) / 2;
        
        // 오버플로우 - 베어낸 나무 길이의 합이 int 범위를 넘을 수 있다.
        long totalHeight = 0;
        for (int tree : trees) {
            if (tree > mid) {
                totalHeight += (tree - mid);
            }
        }
        
        // 나무 길이를 최대 m 만큼 얻는 것이 아니라,
        // 최소 m 이상 얻을 수 있는 최대 높이를 찾는 것
        if (totalHeight >= m) {
            result = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    System.out.println(result);
    sc.close();
}

---

6일만에 처음으로 검색없이, 제한 시간 내에 풀었다.

문제 유형을 분석했던 것이 푸는 데 가장 큰 도움이 되었다.

 

백준 - 2805번 나무 자르기

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