#1448 : 삼각형 만들기

풀이방법

사용된 것:

그리디 알고리즘

정렬

 

2022.01.28 (1)

빨대들을 모두 큰 것부터 정렬한다.

가장 긴 빨대를 1번, 가장 짧은 빨대를 N번이라 부르겠다.

 

일단 1번 빨대와 2번 빨대가 무조건 쓰일 것이라고 가정한다.

3번부터 N번까지 차례차례 살피면서, (2번빨대의 길이) + (j번째 빨대의 길이) > (1번 빨대의 길이) 인 j를 찾는다.

찾아지면 1번, 2번, j번 빨대 세 개로 만드는 삼각형의 변의 합이 정답이다.

 

위의 과정에서 N번 빨대까지 모두 살폈는데 조건에 부합하는 빨대가 없었다면,

2번 빨대와 3번 빨대가 무조건 쓰일 것이라고 가정하고 4번부터 살펴 합당한 j를 찾는다.

 

또 없었다면,

3번 빨대와 4번 빨대가 무조건 쓰일 것이라고 가정하고 5번부터 살핀다.

 

이렇게 N-2번 빨대와 N-1번 빨대가 무조건 쓰일 것이라고 가정하는 경우까지 완료했는데도 합당한 경우가 없었다면,

지금 가진 빨대로는 삼각형을 만들 수 없다. -1을 출력하면 된다.

 

이 알고리즘은 시간초과가 날 줄 알았는데 그렇지 않아 의외였다.

더 빠르게 해결하는 알고리즘이 있는지 살펴보아야겠다.

 

 

 

 

 

 

2022.01.28 (2)

위의 방법에서는 당연히 정답이 될 수 없는 케이스들을 쓸데없이 점검하였다.

 

1번 빨대, 2번 빨대, 3번 빨대가 삼각형을 만들 수 없다면,

4번 빨대 이후의 그 어떤 빨대가 3번 빨대를 대신하든 삼각형을 만들 수가 없다. 4번 이후로 모든 빨대가 3번보다 짧기 때문이다.

 

1번, 2번, 3번 빨대를 점검하고

안 되면 2번, 3번, 4번

또 안 되면 3번, 4번, 5번

...

이렇게만 점검하면 된다.

 

백준 채점 결과에서는 시간이 많이 단축되지는 않았다.

백준이 준비한 테스트케이스 중에서 이 실수에 영향을 받는 경우가 적어서일까?

백준 측도 밀리초까지 신경 쓸 필요 없다는 입장이니 그냥 코드를 효율적으로 정리했다는 점에 만족해야겠다.

 

코드

Java(2022.01.28) (1)

import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.IOException;

import java.util.Arrays;
import java.util.Collections;

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());	//빨대 개수
		Integer[] straws = new Integer[n];			//빨대들의 길이
		for(int i = 0; i<n; i++) {
			straws[i] = Integer.parseInt(br.readLine());
		}
		//긴 것부터 정렬
		Arrays.sort(straws, Collections.reverseOrder());

		for(int i = 0; i<n-2; i++) {
			int a = straws[i];
			int b = straws[i+1];
			
			for(int j = i+2; j<n; j++) {
				if(a<b+straws[j]) {
					System.out.print(a+b+straws[j]);
					System.exit(0);;
				}
			}
			
		}
		
		System.out.print("-1");

	}

}

Java(2022.01.28) (2)

import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.IOException;

import java.util.Arrays;
import java.util.Collections;

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());	//빨대 개수
		Integer[] straws = new Integer[n];					//빨대들의 길이
		for(int i = 0; i<n; i++) {
			straws[i] = Integer.parseInt(br.readLine());
		}
		
		Arrays.sort(straws, Collections.reverseOrder());

		for(int i = 0; i<n-2; i++) {
			int a = straws[i];
			int b = straws[i+1];
			int c = straws[i+2];
			if(a<b+c) {
				System.out.print(a+b+c);
				System.exit(0);;
			}
			
		}
		
		System.out.print("-1");

	}

}