[백준] 2632번 피자판매 (파이썬)

문제링크

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

난이도: GOLD II

문제해결 아이디어

• 하나의 피자에서 나올수 있는 각각의 경우의 수 + 두개의 피자에서 만드는 경우의 수
• 피자 A, 피자 B에서 나올 수 있는 모든 경우의 수를 dict에 저장하였다.
• 하나의 피자의 경우 크기를 만족하는 경우의 수를 합산한다.
• 두개의 피자의 경우 크기의 합이 조건을 만족하는 경우의 수를 서로 곱한다 ex) dic1[2] * dic[5]

소스코드

import sys
from collections import defaultdict

input = sys.stdin.readline

size = int(input())

n,m = map(int, input().split())

a = []
b = []

for _ in range(n):
    a.append(int(input()))

for _ in range(m):
    b.append(int(input()))

def make_dict(arr): # 연속된 숫자 처리 방법 => 리스트를 이어 붙이고 순회 (arr[i:0] + arr[0:i])
    dic = defaultdict(int)

    for i in range(len(arr)):
        tmp = arr[i:] + arr[:i] # 연속된 수 이므로 4 5 1 2 도 포함하기 위해서
        pre = 0
        for num in tmp:
            pre += num
            dic[pre] += 1

    dic[sum(arr)] = 1 # 전체 다 합한 케이스는 1개 뿐이므로
    return dic

dic1 = make_dict(a)
dic2 = make_dict(b)

answer = dic1[size] + dic2[size] # 피자 한판으로 만드는 케이스

for i in range(1, size): # 피자 두판 사용해서 만드는 케이스
    answer += (dic1[i] * dic2[size-i])

print(answer)