[BOJ] 2632 / 피자판매 / Python 파이썬

[BOJ] 2632 / 피자판매 / Python 파이썬

[BOJ] 2632 / 피자판매 / Python 파이썬

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

2632번: 피자판매

 

 

풀이

피자 A 와 B 를 원형 queue 로 설정하고, 이분탐색으로 경우의 수를 구하여 해결하였다.

 

import sys
input = sys.stdin.readline

BUY = int(input())

M, N = map(int, input().split())

A = []
for _ in range(M):
    A.append(int(input()))

B = []
for _ in range(N):
    B.append(int(input()))

A_dic = {}
A_dic[0] = 1
A_dic[sum(A)] = 1
for l in range(1, M):
    s = 0
    e = s+l
    tmp = sum(A[s:e])
    while s < M:
        if tmp not in A_dic:
            A_dic[tmp] = 1
        else:
            A_dic[tmp] += 1

        tmp -= A[s]
        s += 1

        tmp += A[e]
        e += 1
        if e >= M:
            e %= M

res = 0
if BUY in A_dic:
    res += A_dic[BUY]
if BUY - sum(B) in A_dic:
    res += A_dic[BUY-sum(B)]

for l in range(1, N):
    s = 0
    e = s+l
    tmp = sum(B[s:e])
    while s < N:
        if BUY - tmp in A_dic:
            res += A_dic[BUY-tmp]

        tmp -= B[s]
        s += 1

        tmp += B[e]
        e += 1
        if e >= N:
            e %= N

print(res)

※ 쉽게 푼것처럼 설명이 짧았지만, 처음으로 해결한 골드1 문제이다 (무려!!)