[백준] 삼각형 만들기 : 1448번 - Python

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

1448번: 삼각형 만들기

 

 

 

문제를 풀면서 몰랐던 개념

 

- 삼각형이 성립하는 조건

: 어느 두 변의 합이 나머지 변의 합보다 항상 커야 한다!

ex) 각 변의 길이를 x, y ,z라 하고 가장 긴 변의 길이가 z라고 했을 때, x + y > z 를 만족해야 함.

 

 

 

문제의 접근 방법

 

- 삼각형을 빨대가 긴 순서대로 정렬한 후, 가장 긴 3개부터 시작해서 삼각형이 성립하는지 확인하기

만약, 성립하지 않을 경우에는 가장 긴 변을 버리고 다음 변을 가져와서 확인하는 과정을 반복한다.

 

 

 

내가 막혔던 부분

 

- 삼각형이 성립되는 조건에 대한 개념 이해 부족.

- 어차피 내림차순 정렬돼있기 때문에 차례차례 판별해주면 되는데 그걸 생각하지 못하고 값들을 3개씩 따로 추출해서 새로운 리스트에 저장하고 삭제하는 등 의미 없는 반복을 진행함.

- 처음에 시간초과가 나옴.

 

 

 

처음 내가 짠 코드 (오답)

N = int(input())

arr = []
[ arr.append(int(input())) for _ in range(N) ]
arr.sort(reverse=True)	# 길이가 긴 순으로 내림차순 정렬

triangle = []
while True:
    triangle = arr[:3]	# arr의 앞에서 3번째 값까지 triangle에 저장
    del arr[:3]	# triangle에 저장한 값은 arr에서 삭제
    
    # 삼각형 성립 조건이 아니고, 더 이상 비교할 변의 길이가 없을 때
    if len(arr) == 0 and triangle[1] + triangle[2] <= triangle[0]:
        print('-1')	
        
    if triangle[1] + triangle[2] > triangle[0]:	# 삼각형 조건에 성립하면 triangle에 저장돼있는 3개의 값들을 더해주기
        print(sum(triangle))
        break  
        
    else:	# 삼각형 성립 조건이 아니라면
        for i in range(len(arr)):
            del triangle[0]	# 제일 길이가 긴 값(0번째 요소)을 삭제
            triangle.append(arr[0])	# arr에 남아있는 값 중 가장 큰 값(0번째 요소)를 triangle에 추가
            del arr[0]	# triangle에 저장한 값은 arr에서 삭제
            
            if triangle[1] + triangle[2] > triangle[0]:	# 조건이 성립한다면 3개의 값들을 더해주기
                print(sum(triangle))	
                break
    break

 

 

 

수정한 소스코드 (정답)

N = int(input())

arr = []
[ arr.append(int(input())) for _ in range(N) ]
arr.sort(reverse=True)

isTrue = 0	# true, false 판별을 위한 변수

for i in range(len(arr)-2):	# i+2번째까지 비교하기 때문에 전체 길이에서 -2
    if arr[i] < arr[i+1] + arr[i+2]:
        print(arr[i] + arr[i+1] + arr[i+2])	# 삼각형 조건 성립 시 3개의 값 더해서 출력
        isTrue = 1	# 0 -> 1로 값이 바뀜
        break
        
if isTrue == 0:	# 만약 위의 반복문을 거치지 못했다면(isTrue값이 계속 0이라면)
    print(-1)