22945번: 팀 빌딩
능력치가 다 다른 개발자 $N$명이 팀 빌딩을 위해 한 줄로 서있다. 하나의 팀을 만들기 위해서는 개발자 2명이 반드시 모여야 한다. 개발자 A와 개발자 B가 팀을 만들 때 팀의 능력치는 아래와 같
www.acmicpc.net
문제
능력치가 다 다른 개발자 명이 팀 빌딩을 위해 한 줄로 서있다.
하나의 팀을 만들기 위해서는 개발자 2명이 반드시 모여야 한다.
개발자 A와 개발자 B가 팀을 만들 때 팀의 능력치는 아래와 같이 계산이 된다.
- (개발자 A와 개발자 B 사이에 존재하는 다른 개발자 수) × min(개발자 A의 능력치, 개발자 B의 능력치)
예를 들어, 4명의 개발자가 존재할 때, 각 개발자의 능력치를 1 4 2 5라고 하자. 이때 능력치가 1인 개발자와 능력치가 5인 개발자가 한 팀을 이뤘다고 가정하자. 그러면 이 팀의 능력치는 가 된다.
팀 빌딩에서 나올 수 있는 팀 중 능력치의 최대값을 구해보자.
입력
첫 번째 줄에 개발자의 수 이 주어진다.
두 번째 줄에는 의 개발자의 각 능력치 가 공백으로 구분되어 주어진다.
출력
팀의 능력치 최댓값을 출력한다.
코드
n = int(input())
ability = list(map(int, input().split()))
start, end = 0, n-1
ans = 0
while start < end:
if ability[start] < ability[end]:
ans = max(ans, (end-start-1) * ability[start])
start += 1
else:
ans = max(ans, (end-start-1) * ability[end])
end -= 1
print(ans)
투포인터를 이용하여 풀이하였다.
양쪽 포인터 중 작은 능력치를 가진 쪽의 인덱스를 1 증가/감소시키면 된다.
'문제풀이 > 투포인터' 카테고리의 다른 글
[Python/파이썬] 백준 20442번 ㅋㅋ루ㅋㅋ (0) | 2023.06.05 |
---|---|
[Python/파이썬] 백준 20366번 같이 눈사람 만들래? (1) | 2023.04.20 |
[Python/파이썬] 백준 3151번 합이 0 (0) | 2023.04.16 |
[Python/파이썬] 백준 17609번 회문 (0) | 2023.03.26 |
[Python/파이썬] 백준 15961번 회전 초밥 (0) | 2023.02.17 |