[백준 - Python] 22945 - 팀 빌딩

0.  문제 링크

 

 

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

22945번: 팀 빌딩

---

1.  풀이 방법

 

 

1. 정렬할 필요 없음. 정렬을 한다면, 각 개발자의 인덱스도 따로 저장해놔야 함. 결론적으로 인덱스도 맞춰서 계산해야 하므로, 굳이 할 필요가 없음
2. 투 포인터로 양 측 끝부터 시작했음
3. min 값을 수정해야 하므로, min 값이 되는 포인터를 옮겼음
4. 만약 두 개의 값이 같다면 둘 다 옮겼음.
   1. 해당 문제의 경우 하나의 포인터만 옮겨도 정답이 맞음.
   2. 다만 하나의 포인터만 옮기면 반복문을 한 번 더 돌게 됨
   3. 따라서 둘 다 옮겨도 상관은 없음. 자세한 내용은 코드에 주석으로 증명해 놓았음

---

2.  코드

 

 

import sys
input = sys.stdin.readline


if __name__ == "__main__":
    n = int(input())
    maps = list(map(int, input().split()))

    left = 0
    right = n - 1
    val = 0

    while left < right:
        # min 값을 넣으므로, 작은 애의 포인터를 옮기면 된다. 그래야 min 값이 개선될 여지가 보이기 때문
        inner = right - left - 1
        if maps[left] < maps[right]:
            val = max(val, inner * maps[left])
            left += 1
        elif maps[left] > maps[right]:
            val = max(val, inner * maps[right])
            right -= 1
        else:
            val = max(val, inner * maps[left])
            left += 1
            right -= 1
            """
            left += 1을 하고, right -= 1을 해도 괜찮은 이유
            포인터는 현재 양 끝의 3과 3을 가리키고 있는 상태
            
            1. 3 7 ... 9 3 혹은 3 9 ... 7 3
                한 쪽만 옮겨봤자 어차피 3이 min 값임 -> 안의 개발자 개수가 줄기 때문에 손해임 -> 둘 다 옮겨도 상관 없음
            2. 3 2 ... 2 3
                한 쪽만 옮겨봤자 어차피 2가 min 값임 -> 위와 동일
            3. 3 2 ... 9 3
                min 값이 2가 되거나, 3이 됨 -> 기존의 값의 이하가 되기 때문에 손해임 -> 둘 다 옮겨도 상관 없음
            """

    print(val)

---

3.  마무리

 

 

문제를 보면 "능력치가 다 다른 개발자 N명이 팀 빌딩을 위해 한 줄로 서있다." 라고 적혀있는데, 

N은 최대 100,000이고, 능력치는 최대 10,000이다. 필연적으로 중복이 발생한다.

궁금해서 능력치가 같을 때 "raise IndexError"를 시켜봤는데, 예상대로 인덱스 에러가 발생했음.

지문 수정 요청이 있던데,,,,,,,,,,,,,,아직까지 반영이 안 된 것 같음