피자판매 2632번 - Pyton, 부분합

 

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

 

 

코드

 

from collections import Counter

# 피자에서 가능한 부분합을 구하는 함수
def find_sums(pizza, target):
    n = len(pizza)
    sub_sums = Counter()

    for i in range(n):
        sub_sum = 0
        for piece in pizza[i:] + pizza[:i]:  # 원형 배열 순회
            sub_sum += piece
            if sub_sum > target:
                break
            sub_sums[sub_sum] += 1
    if sum(pizza) <= target:
        sub_sums[sum(pizza)] = 1
    return sub_sums

# 입력 처리
target = int(input())
m, n = map(int, input().split())
pizza_A = [int(input()) for _ in range(m)]
pizza_B = [int(input()) for _ in range(n)]

# A, B 피자의 부분합 빈도수 계산
sums_a = find_sums(pizza_A, target)
sums_b = find_sums(pizza_B, target)

result = sums_a[target] + sums_b[target]  # A와 B에서 각각 직접 target을 만드는 경우
for i in range(target):
    result += sums_a[i] * sums_b[target - i]  # A와 B에서 각각 부분합을 더해서 target을 만드는 경우

print(result)

 

 

풀이

 

1. A, B 피자 각각에서 부분합을 구한다!

 

2. 각각의 피자에서 원하는 조각의 크기를 구할 수 있는 경우를 구한다.

 

3. 피자 두개를 섞어 원하는 조각의 크기를 구하는 경우를 구한다.

 

4. 2와 3의 경우를 합친다.

 

 

 

 

다음에 또 봐요