[스위프트][백준 22945][💛골드 4] 팀 빌딩 (투포인터)

🧞‍♂️ 난이도

💛 골드 4

🧞‍♂️ 문제

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

🧞‍♂️ 풀이 방법

투포인터를 이용해서 간단하게 구할 수 있다.

• 배열 양끝에서 투 포인터를 이용해서 안쪽으로 이동시킨다.
• 매번 능력치를 계산해서 최대값을 갱신하고 ( 능력치 = min(left, right) * (right - left - 1))
• 양쪽 포인터 중 작은 수를 가리키는 포인터를 이동시키면 된다

예를 들어서 다음과 같이 배열이 있으면 [4, 9, 5, 10]

• 왼쪽 포인터가 4를 가리키고 오른쪽 포인터가 10을 가리키고 있다
• 그럼 팀의 능력치는 8(min(4, 10) * 2) 이다.
• 그 다음에 왼쪽을 이동시킬건지 오른쪽을 이동시킬건지 정해야되는데..
  • 생각해보면 어차피 두 포인터 중에 작은쪽만 능력치 계산에 이용되기 때문에 무조건 작은 쪽을 이동시켜야 다음에 더 좋은 결과를 얻을 가능성이 생긴다.
• 그럼 그 다음에는 능력치가 9가 된다 (min(9, 10) * 1)

🧞‍♂️ 스위프트 코드

import Foundation

let N = Int(readLine()!)
let numbers = readLine()!.split(separator: " ").compactMap { Int($0) }

var left = 0
var right = numbers.count - 1
var answer = 0
var total = 0

while left < right {
    total = min(numbers[left], numbers[right]) * (right - left - 1)
    answer = max(answer, total)
    if numbers[left] <= numbers[right] {
        left += 1
    } else {
        right -= 1
    }
}

print(answer)

---

맨 위로 이동하기

BOJ 카테고리 내 다른 글 보러가기