📚 2632 - 피자판매

피자 판매

이해

반드시 연속된 조각들을 잘라서 판매한다.
반복문을 통해 풀면 되는 문제이다.
간격이 1씩 앞뒤로 차이가 나니!

(1) 두 피자에서 한쪽 피자로만 줄 수 있는 경우의 수가 존재할 수 있으므로
distA[0] = distB[0] = 1로 주었다.

(2) 피자 한 판에서 나올 수 있는 모든 경우의 수를 구하다 t보다 클 경우 종료

for i in range(m):
    tmp = 0
    for j in range(m):
        tmp += a_arr[(i + j) % m]
        if tmp > t:
            break
        else:
            distA[tmp] = distA.get(tmp, 0) + 1

참고 블로그에서 그림을 보면 알 수 있는데 i, j를 m까지 돌리면서 피자 한판 자체가 m 크기이니 (i + j)를 m으로 나눈 결과의 인덱스 값을 tmp에 더한다.
ex) 1 2 3 4에서 뽑을 때 3, 4, 1(5%4) 와 같이

이렇게 하면 피자 한판에서 나올 수 있는 모든 경우의 수를 구할 수 있다.
(i가 m-1일 경우 m-1, m % m, (m + 1) % m ~)

그리고, 만약 현재까지 합한 값이 찾는 값보다 클 경우, 반복문을 종료한다.

딕셔너리 key 값으로는 현재 덧셈 결과를 저장하고, value에 횟수를 저장한다.

(3) 피자 총합의 누적 개수는 1개로 수정한다. (중복 예외처리)
distA[sum(a_arr)] = distB[sum(b_arr)] = 1

(4) 최종적으로, A 경우의 수 x B 경우의 수로 정답 데이터에 더한다.
ex) 11을 만들어야 한다.
A : 4를 만들 수 있는 경우의 수 : 2 (2 + 2, 1 + 3) 이고
B : 7을 만들 수 있는 경우의 수 : 1 (7) 이라고 할 때

• 2 + 2 + 7 = 1 + 3 + 7 = 11
• 2 x 1 = 2

answer = 0
for i in range(t + 1):
    answer += (distA.get(i, 0) * distB.get(t - i, 0))

소스

import sys

read = sys.stdin.readline

t = int(read())

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

a_arr = []
b_arr = []

for _ in range(m):
    a_arr.append(int(read()))

for _ in range(n):
    b_arr.append(int(read()))

distA = dict()
distB = dict()

distA[0] = distB[0] = 1

# 먼저 a 피자 기준
for i in range(m):
    tmp = 0
    for j in range(m):
        tmp += a_arr[(i + j) % m]
        if tmp > t:
            break
        else:
            distA[tmp] = distA.get(tmp, 0) + 1

# 이제 b 피자 기준
for i in range(n):
    tmp = 0
    for j in range(n):
        tmp += b_arr[(i + j) % n]
        if tmp > t:
            break
        else:
            distB[tmp] = distB.get(tmp, 0) + 1
distA[sum(a_arr)] = distB[sum(b_arr)] = 1

answer = 0
for i in range(t + 1):
    answer += (distA.get(i, 0) * distB.get(t - i, 0))

print(answer)

참고 : https://western-sky.tistory.com/163