algospot 크리스마스 인형 (문제 ID: CHRISTMAS) c++

알고스팟 문제 링크: https://algospot.com/judge/problem/read/CHRISTMAS

algospot.com :: CHRISTMAS

상자마다 인형이 담겨있는 갯수가 각각 다르게 주어졌을때, 아이들k명에게 똑같은 갯수의 인형을 남는 인형 없이 나누어 주려 한다.

주문을 할때 'h번 상자부터 t번 상자까지 다 주세요'(h<=t)라고만 할 수있다.

한번 만 주문할 수 있는 경우 가능한 주문 방법,

한 상자가 주문에 중복으로 포함 되지 않게끔 여러번 주문 할수 있는 경우 최대 주문 횟수, 이렇게 두가지를 구하는 문제이다.

 

h에서 t까지 구입했을때 남기지 않고 나눠줄 수 있는 경우는 (psum[t]-psum[h-1])%k==0인 경우다.

 

한번 만 주문할 수 있는 경우 가능한 주문방법 = 나머지가 같은 것들끼리 묶고, 각 묶음에서 두개를 뽑는 조합의 경우

 

0번부터 i번까지의 상자가 있고, 여러번 주문 할때 최대 주문 횟수를 maxBuys(i)라 할때

maxBuys(i) = max( maxBuys(i-1), maxBuys(j)+1) (이때 j는 psum[i]==psum[j]인 i보다 작은 최댓값)

 

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/17.%20partial%20sum/CHRISTMAS.cpp

GitHub - sbl133/JongmanBook

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2