📍문제 링크
https://www.acmicpc.net/problem/22945
22945번: 팀 빌딩
능력치가 다 다른 개발자 $N$명이 팀 빌딩을 위해 한 줄로 서있다. 하나의 팀을 만들기 위해서는 개발자 2명이 반드시 모여야 한다. 개발자 A와 개발자 B가 팀을 만들 때 팀의 능력치는 아래와 같
www.acmicpc.net
📍알고리즘 분류
- 정렬
- 투 포인터
📍문제 풀이
- 시간 초과를 해결하기 위한 노력1
left와 right 중에서 더 작은 값(min)을 끊임없이 갱신(centering)해가면 된다
만약 큰값을 centering하면, 간격도 좁아지고, 기존 값보다 작아질 수 있기 때문에, 출력할 최댓값을 보존할 수 없기 때문이다
- 시간 초과를 해결하기 위한 노력2
Python에서 변수명을 가능한 짧게 하는 것이 도움이 되는 것 같다
- 시간 초과를 해결하기 위한 노력3
가급적 if, elif 를 통해 조건을 세세하게 따지는 것이 좋지만,
solve를 위해서는 문제에서 괜찮다면 if, else 로만 나누는 것이 좋다
📍코드 (Python)
n = int(input())
t = list(map(int, input().split()))
left = 0
right = n - 1
res = 0
while left + 1 < right:
res = max(res, (right - left - 1) * min(t[left], t[right]))
if t[left] < t[right]:
left += 1
else:
right -= 1
print(res)
📍리뷰
- Node.js로 도저히 해결이 안되면 Python을 사용하자!!
- Python3 로도 해결이 안되면 Pypy3 로 제출해보자