1. 문제 소개

2221. Find Triangular Sum of an Array

2. 나의 풀이법

처음 이 문제를 보았을 때에 각각의 항이 몇 번 반복적으로 더해지는 지를 알 수 있다면 $O(n^2)$까지는 걸리지 않을 것이라고 생각했다.
실제로 이항계수와 관련이 있었고 그렇게 푼 풀이도 맞았다.

import math

class Solution:
    def triangularSum(self, nums: List[int]) -> int:
        answer = 0
        n = len(nums)
        for i in range(n):
            answer = (answer + math.comb(n-1, i) * nums[i]) % 10
        return answer % 10

그러나 이 풀이법은 시간 복잡도는 $O(n)$이지만 math 라이브러리 때문에 조금은 비효율적이다.

3. 다른 풀이법

math 라이브러리를 사용하지 않으면 더욱 빠르게 풀 수 있다.

class Solution:
    def triangularSum(self, nums: List[int]) -> int:
        n=len(nums)-1
        ans, A=nums[0], 1
        for k in range(1, n+1):
            A=A*(n-k+1)//k
            ans=(ans+nums[k]*A)%10
        return ans

4. 결론

이항계수만 잘 안다면 쉽게 풀 수 있는 문제였던 것 같다.