2632. 피자판매 (Python)

2632번: 피자판매

 

풀이

 두 피자별로 구할 수 있는 부분 집합의 피자 조각들의 크기의 합을 구한다. 딕셔너리에 크기의 합별로 구할 수 있는 경우의 수를 카운트해준다. 고객이 원하는 피자의 크기를 target이라고 했을 때, A 피자에서 i (0 <= i <= target) 크기를 사용했을 때의 경우의 수와 B 피자에서 target - i 크기를 사용했을 때의 경우의 수를 사용해서 결과값을 구하면 된다

 

코드

from collections import defaultdict
import sys

input = sys.stdin.readline

# 각 피자의 부분집합의 크기를 구하기 위한 함수 
def getPizzaSum(size, pizza, pizzaDict):
    for i in range(size): # 시작 피자 조각
        pizzaSum = pizza[i]
        pizzaDict[pizzaSum] += 1

        for j in range(1, size - 1): # 시작 피자 조각에서 j개의 피자 조각을 더 사용하는 경우 
            pizzaSum += pizza[(i+j) % size]
            pizzaDict[pizzaSum] += 1

    pizzaDict[0] += 1 # 하나의 피자 조각도 사용하지 않는 경우
    pizzaDict[sum(pizza)] += 1 # 모든 피자 조각을 사용했을 때의 경우


if __name__ == '__main__':
    target = int(input()) # 고객이 원하는 피자의 크기 
    m, n = map(int, input().split()) # m: A 피자의 조각의 수, n: B 피자의 조각의 수 
    aPizza, bPizza = [], [] 
    aPizzaDict, bPizzaDict = defaultdict(int), defaultdict(int) # 각 피자의 경우의 수 카운트

    for i in range(1, m+1):
        aPizza.append(int(input()))

    for j in range(n):
        bPizza.append(int(input()))

    getPizzaSum(m, aPizza, aPizzaDict) # A 피자에 대하여 경우의 수를 구한다.
    getPizzaSum(n, bPizza, bPizzaDict) # B 피자에 대하여 경우의 수를 구한다.

    res = 0

    # A 피자에서 i 크기를 사용했을 때의 경우의 수 * B 피자에서 target - i 크기를 사용했을 때의 경우의 수 
    for i in range(target + 1):
        res += aPizzaDict[i] * bPizzaDict[target - i]

    print(res)