LeetCode [3200]: Maximum Height of a Triangle

📌 LeetCode [3200]: Maximum Height of a Triangle

---

문제 설명 📄

빨간색 블록의 개수를 나타내는 red와 파란색 블록의 개수를 나타내는 blue가 주어집니다.
삼각형의 높이를 최대화하려고 합니다.

삼각형의 규칙은 다음과 같습니다:

1. 각 층의 블록 수는 층의 번호와 동일합니다. 예: 첫 번째 층은 1개의 블록, 두 번째 층은 2개의 블록.
2. 삼각형은 빨간 블록 또는 파란 블록으로 시작하여 층마다 번갈아가며 쌓습니다.
3. 특정 층을 쌓기에 블록이 부족하면 삼각형은 중단됩니다.

---

문제 해결 접근 💡

1. 블록 사용 규칙 분석:
   • 빨간 블록과 파란 블록이 교대로 사용되므로, 두 가지 경우를 시뮬레이션:
     • 빨간 블록으로 시작하는 경우.
     • 파란 블록으로 시작하는 경우.
2. 삼각형 높이 계산:
   • n번째 층에서는 n개의 블록이 필요합니다.
   • 블록이 부족하면 삼각형 쌓기를 중단합니다.
   • 두 경우 중 더 큰 삼각형의 높이를 반환합니다.

---

Solution 💻

class Solution:
    def maxHeightOfTriangle(self, red: int, blue: int) -> int:
        def find(fRed, fBlue, start):
            count = 1
            result = 0
            while True:
                if start:
                    if (fRed - count) < 0:
                        return result
                    fRed -= count
                else:
                    if (fBlue - count) < 0:
                        return result
                    fBlue -= count
                count += 1
                result += 1
                start = not start

        return max(find(red, blue, True), find(red, blue, False))

시간 복잡도 ⏲️

• 단일 시뮬레이션: O(√n), 여기서 (n)은 총 블록의 개수입니다.
• 전체 복잡도: O(√n).

공간 복잡도 🗄️

• 추가 공간 사용 없음: (O(1)).