백준 2632번 - 피자판매

출처 : 2632번: 피자 판매 (acmicpc.net) 

2632번: 피자판매

 

---

 

피자판매 성공출처분류

시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율

2 초

128 MB

2715

1029

673

35.893%

문제

고객이 두 종류의 피자 A와 B를 취급하는 피자가게에서 피자를 주문하고자 한다. <그림 1>과 같이 각 종류의 피자는 다양한 크기의 여러 개의 피자 조각으로 나누어져 있다. 각 조각에 쓰인 숫자는 피자 조각의 크기를 나타낸다.

고객이 원하는 피자의 크기를 이야기하면, 피자가게에서는 한 종류의 피자를 2 조각 이상 판매할 때는 반드시 연속된 조각들을 잘라서 판매한다. 이때 판매한 피자조각의 크기 합이 주문한 크기가 되어야 한다. 판매한 피자 조각은 모두 A종류이거나, 모두 B종류이거나, 또는 A와 B 종류가 혼합될 수 있다. 예를 들어서, <그림 1>과 같이 잘라진 피자가 있을 때, 손님이 전체 크기가 7 인 피자를 주문하면, 피자 가게에서는 <그림 2>와 같이 5 가지 방법으로 피자를 판매할 수 있다.

피자가게에서 손님이 원하는 크기의 피자를 판매하는 모든 방법의 가지 수를 계산하는 프로그램을 작성하시오

입력

첫 번째 줄에는 손님이 구매하고자 하는 피자 크기를 나타내는 2,000,000 이하의 자연수가 주어진다. 두 번째 줄에는 A, B 피자의 피자 조각의 개수를 나타내 는 정수 m, n 이 차례로 주어진다 (3 ≤ m, n ≤ 1000). 세 번째 줄부터 차례로 m 개의 줄에는 피자 A의 미리 잘라진 피자조각의 크기를 나타내는 정수가 주어진다. 그 다음 n 개의 줄에는 차례로 피자B의 미리 잘라진 피자조각의 크기를 나타내는 정수가 주어진다. 각 종류의 피자조각의 크기는 시계방향으로 차례로 주어지며, 각 피자 조각의 크기는 1000 이하의 자연수이다.

출력

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

 

---

[ 문제 설명 ]

 

수기와 그림으로 설명하겠음

 

그림 1 - 문제 풀이 아이디어

그림 2 - 문제 풀이 아이디어

그림 3 - 문제 풀이 아이디어

 

---

[ 코드 ]

 

import sys

target = int(sys.stdin.readline().rstrip())
m, n = map(int, sys.stdin.readline().split())
left = [int(sys.stdin.readline().rstrip()) for _ in range(m)]
right = [int(sys.stdin.readline().rstrip()) for _ in range(n)]

left_sum, right_sum = [0] * 2000001, [0] * 2000001
left_sum[0] = right_sum[0] = 1
left_len, right_len = len(left), len(right)
for i in range(left_len):
    s = 0
    
    for j in range(left_len):
        s += left[(i + j) % m]
        
        if s > target:
            break
        else:
            left_sum[s] += 1

for i in range(right_len):
    s = 0
    for j in range(right_len):
        s += right[(i + j) % n]
        if s > target:
            break
        else:
            right_sum[s] += 1

# 한 쪽에서 여러개의 합으로 하나의 target에 도달 하는 경우.(예외 처리)
left_sum[sum(left)] = right_sum[sum(right)] = 1


ans = 0
for i in range(target + 1):
    ans += (left_sum[i] * right_sum[target - i])
print(ans)

 

 

---

후기

 

key, value를 이용하는 거에 이제 익숙해진 듯하다.

 

읽어 내려가는데 불편함이 확실이 적어졌다.