[백준] 트리의 지름 (1967번)

코드 힌트

1. 문제 이해:
   • 목표 값 num을 만드는 연속된 자연수의 수열을 찾아야 합니다.
   • 수열의 길이(count)가 최소부터 시작해 점차 늘려가며 가능한 경우를 찾습니다.
   • 최대 길이 100까지 시도하고, 목표 값을 만드는 수열이 없으면 -1을 출력합니다.
2. 핵심 아이디어:
   • 주어진 숫자열의 중앙값(middle)을 중심으로 시작점을 계산합니다.
   • 길이가 짝수인 경우와 홀수인 경우를 나눠 시작 위치를 조정합니다.
   • 연속된 숫자들의 합이 목표 값과 같으면 그 수열을 출력합니다.
3. 알고리즘 흐름:
   • 수열의 중앙값을 기준으로 시작점 계산.
   • 연속된 숫자열의 합과 목표 값(num)을 비교.
   • 길이를 늘려가며(최대 100까지) 모든 경우 탐색.

---

정답은 더보기 클릭

import java.util.*;

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

        // 입력: 찾고자 하는 합 (num)과 연속된 정수의 최소 개수 (count)
        int num = in.nextInt();  // 목표 합
        int count = in.nextInt(); // 최소 연속된 숫자 개수

        // 연속된 숫자의 개수(count)가 100 이하일 때까지 반복
        while (count <= 100) {
            int middle = num / count; // 중앙값 계산
            
            int sum = 0; // 연속된 숫자의 합을 저장할 변수

            // 연속된 숫자열의 시작점 계산
            int start = middle - count / 2;

            if (count % 2 == 0) { // count가 짝수인 경우
                start++; // 짝수 개수일 경우, 시작값을 한 칸 오른쪽으로 이동

                // 연속된 숫자들의 합 계산
                for (int i = start; i < start + count; i++) {
                    sum += i;
                }
            } else { // count가 홀수인 경우
                // 연속된 숫자들의 합 계산
                for (int i = start; i < start + count; i++) {
                    sum += i;
                }
            }

            // 목표 값과 합이 일치하면 결과 출력
            if (sum == num) {
                printArr(start, count); // 정답 출력 함수 호출
                return; // 프로그램 종료
            } else {
                count++; // count를 증가시켜 다음 경우 탐색
            }
        }

        // 조건에 맞는 연속된 숫자열을 찾지 못하면 -1 출력
        System.out.println(-1);
    }

    // 연속된 숫자열을 출력하는 함수
    public static void printArr(int start, int count) {
        if (start < 0) { // 시작 값이 음수일 경우, -1 출력
            System.out.println(-1);
            return;
        }

        // 숫자열을 문자열로 만들어 출력
        String msg = "";
        for (int i = start; i < start + count; i++) {
            msg += i + " "; // 각 숫자 뒤에 공백 추가
        }

        msg = msg.trim(); // 문자열의 마지막 공백 제거
        System.out.println(msg); // 결과 출력
    }
}