BOJ 2632 피자판매

https://www.acmicpc.net/problem/2632
시간 2초, 메모리 128MB
input :

• 피자크기를 나타내는 2,000,000 이하의 자연수
• m, n 이 차례로 주어진다 (3 ≤ m, n ≤ 1000)
• m 개의 줄에는 피자 A의 미리 잘라진 피자조각의 크기를 나타내는 정수
• n 개의 줄에는 차례로 피자B의 미리 잘라진 피자조각의 크기를 나타내는 정수

output :

• 피자를 판매하는 방법의 가지 수를 나타내는 정수를 출력한다. 피자를 판매하는 방법이 없는 경우에는 숫자 0을 출력한다.

조건 :

• 한 종류의 피자를 2 조각 이상 판매할 때는 반드시 연속된 조각들을 잘라서 판매
• 판매한 피자조각의 크기 합이 주문한 크기

---

가장 중요한 것.
피자 A에서의 조각으로만 팔수도
피자 B에서의 조각으로만 팔수도
피자 A와 B의 혼합으로 팔수도 있다.

그렇다면 피자 A도 공집합이, B도 공집합이 존재해야 하기 때문에 dict에 key가 0인 놈을 1로 만들어 준다.

sub_a = defaultdict(int)
sub_b = defaultdict(int)

sub_a[0] = 1
sub_b[0] = 1

그리고 피자의 경우 연속적인 합이 존재하는데 , 모든 원소들의 합은 1가지 경우밖에 존재하지 않는다. 이를 예외처리 해주자.

sub_a[sum(a)] = 1
sub_b[sum(b)] = 1

그러면 인제 연속합을 구하자.

평소의 경우
0 ~ 5
1 ~ 5
2 ~ 5 ... 처럼 앞의 부분이 줄어 들게 만들어 주었지만.

지금은
0 ~ 5
1 ~ 6
2 ~ 7 ... 처럼 같이 늘어나야 한다.
i는 계속 증가하고 , j의 범위가 계속 똑같이 유지되게 해주어야 한다.
그리고 늘어난 길이는 나머지 연산을 통해 다시 0부터 시작하도록 하자.

for i in range(n):
    temp = 0
    for j in range(n):
        temp += b[(i + j) % n]
        if temp > target:
            break
        else:
            sub_b[temp] += 1

import sys
from collections import defaultdict

target = int(sys.stdin.readline())
m, n = map(int, sys.stdin.readline().split())
a, b = [], []

for i in range(m):
    a.append(int(sys.stdin.readline()))
for i in range(n):
    b.append(int(sys.stdin.readline()))

sub_a = defaultdict(int)
sub_a[0] = 1
sub_b = defaultdict(int)
sub_b[0] = 1

for i in range(m):
    temp = 0
    for j in range(m):
        temp += a[(i + j) % m]
        if temp > target:
            break
        else:
            sub_a[temp] += 1

for i in range(n):
    temp = 0
    for j in range(n):
        temp += b[(i + j) % n]
        if temp > target:
            break
        else:
            sub_b[temp] += 1

sub_a[sum(a)] = 1
sub_b[sum(b)] = 1

ans = 0
for key in sub_a:
    aim = target - key
    if sub_b.get(aim):
        ans += sub_a[key] * sub_b[aim]
print(ans)