탭고리즘 2024-12-23 막대기 삼각형의 최대 개수

 

• 문제설명
  숫자 N을 입력받은 후 다음 입력으로 N만큼의 숫자를 입력받는다. 이 입력받은 여러 개의 숫자들 중에서 3개를 골라 서로 다른 삼각형을 만들 수 있는 최대 개수를 구해 출력하면 된다.

• 제출코드     

import java.util.Arrays;
import java.util.Scanner;

public class MaxTriangles {

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

        int N = scanner.nextInt(); // 막대기의 개수
        int[] sticks = new int[N]; // 막대기의 길이 배열

        for (int i = 0; i < N; i++) {
            sticks[i] = scanner.nextInt(); // 각 막대기 길이 입력
        }

        // 최대 삼각형 조합의 개수를 출력
        System.out.println(maxTriangles(sticks));
    }

    // 주어진 막대기들로 만들 수 있는 삼각형의 최대 개수를 구하는 함수
    public static int maxTriangles(int[] sticks) {
        Arrays.sort(sticks); // 막대기들을 오름차순으로 정렬

        int count = 0; // 삼각형의 개수를 저장할 변수

        // 가장 긴 막대기부터 시작해서 삼각형을 만들 수 있는지 확인
        for (int i = sticks.length - 1; i >= 2; i--) {
            int c = sticks[i]; // 가장 긴 막대기의 길이
            int a = 0, b = i - 1; // 남은 두 막대기의 시작(a)과 끝(b) 인덱스

            // a와 b를 조정하면서 가능한 삼각형을 찾음
            while (a < b) {
                // 두 짧은 막대기의 합이 가장 긴 막대기보다 크다면 삼각형을 만들 수 있음
                if (sticks[a] + sticks[b] > c) {
                    count += b - a; // 가능한 조합의 개수는 (b - a)
                    b--; // 다음 조합을 찾기 위해 b를 왼쪽으로 이동
                } else {
                    a++; // 조건을 만족하지 않으면 a를 오른쪽으로 이동
                }
            }
        }

        return count; // 가능한 삼각형의 개수 반환
    }
}

 

코드설명

삼각형의 성질을 먼저 살펴보자면 서변중 가장 긴 변의 길이가 남은 두 변의 길이의 합보다 커야 삼각형이 성립한다. 
이 성질을 이용하기 위해 먼저 입력받은 배열을 정렬해 준다. 정렬을 하기 위해서는 Arrays.sort를 사용했다.
가장 긴 변을 설정해주기 위해서 for문을 마지막 인덱스부터 역으로 돌렸다. c에 가장 긴 변의 길이를 저장하고 a = 0, b = i-1을 통해서 각각 첫 번째 인덱스와 마지막 직전의 인덱스를 저장해 두었다. 
그리고 a가 b보다 작을 때 다음 구문을 진행했다.

if (sticks[a] + sticks [b] > c) {
                    count += b - a; // 가능한 조합의 개수는 (b - a)
                    b--; // 다음 조합을 찾기 위해 b를 왼쪽으로 이동
                } else {
                    a++; // 조건을 만족하지 않으면 a를 오른쪽으로 이동
                }

 

가장 긴변의 길이가 c에 저장되어 있고 가장 짧은 변 a, 그리고 c보다 하나 직전의 변인 b 이 둘의 합이 c보다 크면 삼각형이 성립된다. 
만약에 sticks[a] + sticks [b] > c 이게 성립한다면 a와 b사이에 있는 값들은 모두 성립하기 때문에 삼각형이 되는 경우의 수를 저장할 count변수에 b - a를 저장해 준다. 따지면 이는 a를 b전까지 증가하면서 구한 삼각형의 경우의 수를 더해준 거와 마찬가지 이므로 b--를 진행해 준다. 
만약 위 조건문을 성립하지 않는다면 가장 짧은 변의 길이를 나타내는 인덱스인 a를 증가시켜 다음 긴 변부터 다시 조건문을 확인한다.