[백준][부분합] 2632. 피자판매

2632. 피자판매

 

 

• 첫 풀이 - 메모리 초과 fail
  • idx_set으로 동일한 조합이 있는지 모아서 확인했더니 메모리 터짐
  • ⇒ arr[i:] + arr[:i] 이런식으로 해야 중복 조합이 안생긴다

•  

from collections import defaultdict, deque

k = int(input()) 

def partial(lst, n): 
	global k
    """ 원형 배열의 모든 연속 부분합을 계산하고, 중복을 방지 """
    dp = deque(lst)
    pizza = defaultdict(int)  # 합을 만드는 경우의 수 카운트
    idx_set = set()  # 선택된 조각 인덱스를 집합으로 변환하여 중복 방지를 위한 집합
    
    for start in range(n): 
        total = 0
        tmp = set()
        for i in range(n): 
            total += dp[i]
            tmp.add((start + i) % n)  # 선택한 조각의 인덱스를 추가
            if total > k:  # 목표값 k를 초과하면 중단
                break
            # 인덱스 집합을 정렬된 튜플로 변환 (정렬된 형태로 중복 체크)
            index_tuple = tuple(sorted(tmp))  # set을 정렬 후 튜플로 변환
            if index_tuple not in idx_set:
                pizza[total] += 1  # total을 만드는 경우의 수를 1 추가
                idx_set.add(index_tuple)  # 중복 방지를 위해 추가
        dp.rotate(-1)  # 원형 리스트 회전
    
    return pizza

# 입력 받기
m, n = map(int, input().split()) 
alst = [int(input()) for _ in range(m)] 
blst = [int(input()) for _ in range(n)] 

# A와 B의 연속 부분합을 구하기
countA = partial(alst, m) 
countB = partial(blst, n) 

# 경우의 수 계산
result = countA[k] + countB[k]  # A 단독, B 단독으로 k를 만드는 경우 
for i in range(1, k):  # i + j = k를 만족하는 모든 i, j의 조합 계산 
    result += countA[i] * countB[k - i]

# 결과 출력
print(result)

 

 

• 풀이
  • 부분합

📍 부분합
⇒ 원형 배열의 모든 연속 부분합을 계산해서 값이 만들어질 수 있는 경우의 수 세기

• set을 정렬하는 방법
  • sorted(set) => list로 반환됨
  • 그걸 다시 tuple로 변환하면 가능
  • tuple(sorted(set))
• lst[start:] + lst[:start] 하면 순환하면서 전체리스트 확인
  • 피자 통으로 선택하는 경우 → 1로 수정해주기

from collections import defaultdict

k = int(input())
m, n = map(int, input().split())
alst = [int(input()) for _ in range(m)]
blst = [int(input()) for _ in range(n)]

def partial(lst):
    global k
    # 원형 배열의 모든 연속 부분합을 계산
    length = len(lst)
    pizza = defaultdict(int)  # key값을 만들 수 있는 경우의 수

    for start in range(length):
        total = 0
        for now in lst[start:] + lst[:start]:  # 원형 리스트처럼 순환하며 조각을 탐색
            total += now
            if total > k:  # 목표값 k를 초과하면 중단
                break
            pizza[total] += 1  # total을 만드는 경우의 수 추가
            
    if sum(lst)<=k:
        pizza[sum(lst)]=1

    return pizza

# A 단독, B 단독으로 k를 만드는 경우
countA = partial(alst)
countB = partial(blst)

result = countA[k] + countB[k]

# A, B 합쳐서 고를 경우
for i in range(1, k):
    result += countA[i] * countB[k - i]

# 결과 출력
print(result)