[Python] 백준 14929 - 귀찮아(SIB) 문제 풀이

Overview

BOJ 14929번 귀찮아 (SIB) Python 문제 풀이
분류: Prefix Sum (누적합)

문제 페이지

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

백트래킹으로 모든 경우를 더해나가면 시간초과가 발생한다.

풀이 코드 1

from sys import stdin


def main():
    def input():
        return stdin.readline().rstrip()

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

    prefix_sum = 0
    res = 0
    for i in range(len(nums) - 1, 0, -1):
        prefix_sum += nums[i]
        res += nums[i - 1] * prefix_sum

    print(res)


if __name__ == "__main__":
    main()

문제에서 주어진 식은 분배법칙을 이용하여 다음과 같이 나타낼 수 있다.

따라서 주어진 숫자들에서 거꾸로 누적합을 구하면 답을 구할 수 있다.

풀이 코드 2

from sys import stdin


def main():
    def input():
        return stdin.readline().rstrip()

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

    prefix_sum = 0
    res = 0
    for i in range(len(nums) - 1):
        prefix_sum += nums[i]
        res += nums[i + 1] * prefix_sum

    print(res)


if __name__ == "__main__":
    main()
    

이전 풀이에서 굳이 거꾸로 누적합을 구할 필요는 없다. 다음과 같이 조건 식을 변형할 수 있기 때문이다.

식에서 각 원소는 동일한 개수만큼 사용되므로 순차적으로 누적합을 구하며 답을 구할 수 있다.