-
1448. [Python]삼각형 만들기Python_알고리즘/Silver III 2023. 6. 6. 21:19
1. 문제
https://www.acmicpc.net/problem/1448
1448번: 삼각형 만들기
첫째 줄에 빨대의 개수 N이 주어진다. N은 3보다 크거나 같고, 1,000,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 빨대의 길이가 한 줄에 하나씩 주어진다. 빨대의 길이는 1,000,000보다
www.acmicpc.net
2. 접근 방법
- 시간 제한: 2초
- 메모리 제한: 128MB
- 정렬
- 그리디 알고리즘
3. 파이썬 코드
import sys # input 값이 많으므로 sys 사용 input = sys.stdin.readline N = int(input()) # input 값을 담을 리스트 num_list = [] for _ in range(N): num_list.append(int(input())) # 내림차순 정렬 num_list.sort(reverse=True) # N-2 값까지 반복문 시행 for i in range(N-2): # 삼각형의 제일 긴 변의 길이가 다른 두변의 합보다 작아야 삼각형이 된다. if num_list[i] < num_list[i+1] + num_list[i+2]: print(num_list[i]+num_list[i+1]+num_list[i+2]) break # 그 외의 경우 -1 출력 else: print(-1)
4. 문제를 풀고난 후 생각
- 삼각형을 만들기 위해서는 삼각형을 이루는 조건을 먼저 생각해야 한다.
- 삼각형이 되기 위해서는 제일 긴 변의 길이가 다른 두변의 길이의 합보다 작아야 삼각형을 이룰 수 있다.
- 문제에서는 세 변의 길이 합의 최대를 구하라 했으므로 들어온 input 값을 내림차순 정렬한 후 인덱스를 기준으로 +1 +2 한 인덱스 의 값들과 비교를 해가며 삼각형을 이루는지 못이루는지 등을 판단하며 반복문을 진행해 가면 구할 수 있다.
- 만약 원하는 조건을 달성할 경우 break 를 통해서 불필요한 연산을 하지 않도록 해준다.
5. 문제를 푸는데 도움이 되는 지식
- 그리디 알고리즘
- 정렬
'Python_알고리즘 > Silver III' 카테고리의 다른 글
2346. [Python]풍선 터뜨리기 (2) 2023.06.13 2371. [Python]파일 구별하기 (1) 2023.06.11 1904. [Python]01타일 (0) 2023.06.05 2312. [Python]수 복원하기 (8) 2023.06.04 1270. [Python]전쟁 - 땅따먹기 (0) 2023.05.30