문제 링크

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

문제 설명

• 주문이 들어오면 한 피자에서 인접한 조각들만 자를 수 있다
• 각 조각의 크기가 다르다
• A 피자, B 피자에서 조각을 잘라 특정 크기를 만들 수 있는 경우의 수 출력

풀이

순서

• A 피자로 만들 수 있는 조각 크기의 경우의 수 카운트
• B 피자로 만들 수 있는 조각 크기의 경우의 수 카운트
• 합이 요청 크기인 경우 누적
  • A의 경우의 수 * B의 경우의 수

경우의 수 카운트 구현 방법

• 크기 0을 만들 수 있는 경우의 수 1
• 크기 최대를 만들 수 있는 경우의 수 1
• 현재 인덱스를 i라 할 때
• 직전 인덱스를 카운트하지 않아야 함
• 큐에 넣은 후 i번 rotate & 1회 pop
• 하나씩 popleft 하며 경우의 수 += 1

시간복잡도

• 조각의 수를 n이라 할 때 (1 <= n <= 1000)
• 특정 조각을 시작으로 하는 인접한 조각의 경우의 수 탐색 (n번 탐색)
• 총 O(n**2) -> 1,000,000
• 총 경우의 수 카운트 -> O(n) -> 2,000,000

코드

from collections import deque
import sys
ipt = sys.stdin.readline


def init():
    total = int(ipt())
    m, n = map(int, ipt().split())
    a = [int(ipt()) for _ in range(m)]
    b = [int(ipt()) for _ in range(n)]
    return a, m, b, n, total
    

def get_count(a, m):
    count_a = [0] * (sum(a) + 1)
    count_a[0] = 1
    count_a[-1] = 1
    for i in range(m):
        q = deque(a)
        for _ in range(i):
            q.rotate(-1)
        q.pop()
        summ = 0
        while q:
            summ += q.popleft()
            count_a[summ] += 1
    return count_a


a, m, b, n, total = init()
count_a = get_count(a, m)
count_b = get_count(b, n)
answer = 0
for i in range(total + 1):
    j = total - i
    if 0 <= i < len(count_a) and 0 <= j < len(count_b):
        answer += count_a[i] * count_b[j]
print(answer)