(Python/🥇4)백준알고리즘 22945번: 팀 빌딩

 

문제 바로가기 

팀 빌딩

문제:

개발자 N명이 팀 빌딩을 위해 한 줄로 서있다. 하나의 팀을 만들기 위해서는 개발자 2명이 반드시 모여야 한다. 개발자 A와 개발자 B가 팀을 만들 때 팀의 능력치는 아래와 같이 계산이 된다.

• (개발자 A와 개발자 B 사이에 존재하는 다른 개발자 수) × min(개발자 A의 능력치, 개발자 B의 능력치)

예를 들어, 4명의 개발자가 존재할 때, 각 개발자의 능력치를 1 4 2 5라고 하자. 이때 능력치가 1인 개발자와 능력치가 5인 개발자가 한 팀을 이뤘다고 가정하자. 그러면 이 팀의 능력치는 2×min(1, 5) = 2가 된다. 팀 빌딩에서 나올 수 있는 팀 중 능력치의 최대값을 구해보자.

입력:

첫 번째 줄에 개발자의 수 N이 주어진다. 두 번째 줄에는 N의 개발자의 각 능력치 x_{i}가 공백으로 구분되어 주어진다.

 

출력:

팀의 능력치 최댓값을 출력한다.

풀이:

시간초과 코드

import sys

sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

n = int(input())
ability = list(map(int,input().split()))
res = 0
for i in range(n):
    for j in range(i+1,n):
        res = max(res,(j-i-1) * min(ability[j], ability[i]))
print(res)

 

풀이2:

import sys

sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

n = int(input())
ability = list(map(int,input().split()))

left = 0; right = n-1
res = 0
while left + 1 < right:
    # 인원수는 최대임, 그 다음은 작은 숫자의 포인터를 없애야함 그래야 큰 값으로 바뀌어 그 중 작은 숫자를 고름
    res = max(res, (right-left -1) * min(ability[left],ability[right]))
    if ability[left] < ability[right]:
        left += 1
    else:
        right -= 1
print(res)

 

시작순서를 맨 처음 인덱스와, 맨 마지막 인덱스로 맞춰준다. 그럼 인원수는 최대인 상태이다. 그리고 min값을 구해준다.

그 다음부터 인원수는 무조건 줄게되고

left, right 를 옮길때 가장 큰 값이 나오도록 포인트를 옮겨줘야하는데

그 조건이 이 두수중 작은 수를 바꿔줘야 한다.

예를들어 3,7 일때 7 을 없애주면 3,5 혹은 3,9 이렇게 되어 무조건 min값은 3이지만

3을 없애 1,7 혹은 5,7 이면 min 값은 1 ,5로 큰 값이 나올 수 있다.