[SWEA/Java] 나무 높이 (14510)

나무 높이 (14510)

1. 문제 분석

문제 개요

• 나무의 높이를 조정하여 모든 나무를 최대 높이로 맞추기 위해 필요한 최소 일수를 계산하는 문제이다.

입력 형식

• 첫 번째 줄에 테스트 케이스의 수 T가 주어진다.
• 다음 T개의 줄 각각에는 나무의 개수 N과 N개의 나무 높이가 주어진다.

출력 형식

• 각 테스트 케이스에 대해, 모든 나무를 최대 높이로 맞추기 위해 필요한 최소 일수를 출력한다.

2. 알고리즘 종류

이 문제는 수학적 계산과 구간 탐색을 사용하여 해결하는 문제이다. 나무의 높이 차이에 따라 필요한 일수를 계산하고, 가장 많은 일수를 필요한 나무를 기준으로 최소 일수를 구한다.

3. 주요 부분 및 코드 작성 방법

1. 나무의 높이와 최대 높이 계산

• 나무의 높이를 입력받고 최대 높이를 계산한다.

2. 각 나무를 최대 높이로 맞추기 위한 최소 일수 계산

• 각 나무의 높이와 최대 높이의 차이를 계산하여, 필요한 일수를 구한다.

3. 결과 출력

• 계산된 최대 일수를 출력하여 결과를 제공한다.

4. 코드 설명

(1) 메인 함수 (main)

• 입력 처리

    Scanner sc = new Scanner(System.in); // Scanner 객체 생성
    int T = sc.nextInt(); // 테스트 케이스 수 입력

  • Scanner 객체를 생성하여 입력을 처리한다.
  • 테스트 케이스 수 T를 입력받는다.

• 나무의 높이와 최대 높이 계산

    for (int tc = 1; tc <= T; tc++) { // 각 테스트 케이스 처리
        int N = sc.nextInt(); // 나무의 개수 입력
        int[] heights = new int[N]; // 나무의 높이를 저장할 배열 생성
        int maxHeight = 0; // 최대 높이 초기화
  
        for (int i = 0; i < N; i++) {
            heights[i] = sc.nextInt(); // 나무의 높이 입력
            if (heights[i] > maxHeight) {
                maxHeight = heights[i]; // 최대 높이 갱신
            }
        }

  • 각 테스트 케이스마다 나무의 개수와 높이를 입력받아 최대 높이를 계산한다.

• 모든 나무를 최대 높이로 맞추기 위한 최소 일수 계산

        int maxDays = 0; // 필요한 최대 일수 초기화
        for (int i = 0; i < N; i++) {
            int delta = maxHeight - heights[i]; // 현재 나무의 높이와 최대 높이의 차이 계산
            int days = 0; // 일수 초기화
  
            if (delta % 3 == 0) {
                days = (delta / 3) * 2; // delta를 3으로 나눈 몫에 2를 곱하여 일수 계산
            } else if (delta % 3 == 1) {
                days = (delta / 3) * 2 + 1; // delta를 3으로 나눈 몫에 2를 곱하고 나머지 1일 때 추가 1 더함
            } else {
                days = (delta / 3) * 2 + 2; // delta를 3으로 나눈 몫에 2를 곱하고 나머지 2일 때 추가 2 더함
            }
  
            if (days > maxDays) {
                maxDays = days; // 최대 일수 갱신
            }
        }

  • 나무를 최대 높이로 맞추기 위해 필요한 일수를 계산하고, 최대 일수를 업데이트한다.

• 결과 출력

        System.out.println("#" + tc + " " + maxDays); // 결과 출력
    }
  
    sc.close(); // Scanner 객체 닫기

  • 각 테스트 케이스의 결과를 출력하고, Scanner 객체를 닫아 자원을 해제한다.

5. 전체 코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in); // Scanner 객체 생성
        int T = sc.nextInt(); // 테스트 케이스 수 입력

        for (int tc = 1; tc <= T; tc++) { // 각 테스트 케이스 처리
            int N = sc.nextInt(); // 나무의 개수 입력
            int[] heights = new int[N]; // 나무의 높이를 저장할 배열 생성
            int maxHeight = 0; // 최대 높이 초기화

            // 나무의 높이와 최대 높이 계산
            for (int i = 0; i < N; i++) {
                heights[i] = sc.nextInt(); // 나무의 높이 입력
                if (heights[i] > maxHeight) {
                    maxHeight = heights[i]; // 최대 높이 갱신
                }
            }

            // 모든 나무를 최대 높이로 맞추기 위한 최소 일수 계산
            int maxDays = 0; // 필요한 최대 일수 초기화
            for (int i = 0; i < N; i++) {
                int delta = maxHeight - heights[i]; // 현재 나무의 높이와 최대 높이의 차이 계산
                int days = 0; // 일수 초기화

                // delta를 3으로 나눈 몫과 나머지를 통해 필요한 일수를 계산
                if (delta % 3 == 0) {
                    days = (delta / 3) * 2; // delta를 3으로 나눈 몫에 2를 곱하여 일수 계산
                } else if (delta % 3 == 1) {
                    days = (delta / 3) * 2 + 1; // delta를 3으로 나눈 몫에 2를 곱하고 나머지 1일 때 추가 1 더함
                } else {
                    days = (delta / 3) * 2 + 2; // delta를 3으로 나눈 몫에 2를 곱하고 나머지 2일 때 추가 2 더함
                }

                // 최대 일수 업데이트
                if (days > maxDays) {
                    maxDays = days; // 최대 일수 갱신
                }
            }

            // 결과 출력
            System.out.println("#" + tc + " " + maxDays); // 결과 출력
        }

        sc.close(); // Scanner 객체 닫기
    }
}