알고리즘 문제 해결 전략2 17장 부분 합(2)

17.2문제: 크리스마스 인형

산타 할아버지는 한 번 주문할 때마다, 주문한 상자에 있는 인형들을 모두 꺼내서 각각을 K명에게 정확히 같은 수만큼 나누어 주고, 남는 인형이 없도록 함.

 

17.3 풀이: 크리스마스 인형

두 가지의 서로 다른 부분 문제로 구성됨. 두 문제는 모두 부분 합을 이용해서 풀 수 있음. 어린이들에게 인형을 모두 나눠주려면 인형의 총수가 K의 배수여야 함. 

(psum[T] - psum[H-1]) mod K = 0 이것을 전개하면

psum[T] mod K = psum[H-1] mod K

psum[]에서 중요한 것은 K로 나눈 나머지일 뿐이라는 사실을 알 수 있음. 따라서 이 문제는 psum[]을 아래와 같이 정의함. 이 아이디어는 이 문제를 해결하는 데 중심 역할을 함.

 

구입할 수 있는 방법의 수 계산하기

H번째부터 T번째 상자까지를 주문했을 때 K명의 어린이에게 모두 나눠줄 수 있다는 말은 항상 psum[H-1] = psum[T]라는 뜻임. 따라서 psum[]의 각 원소를 모두 같은 것끼리 모읍시다. 이들 중 두개를 선택하면 한 번의 주문이 됨. 

 

겹치지 않고 구입할 수 있는 최대 횟수 계산하기

부분 합을 이용한 동적 계획법으로 풀 수 있음. 서로 겹치지 않는 부분 구간을 가장 많이 골라는 함수를 다음과 같이 정의함. maxBuys(i)=0번 상자부터 i번 상자까지의 범위 내에서 서로 겹치지 않고 구매할 수 있는 부분 구간의 최대 수. 우선 완전  탐색 알고리즘을 만들기 위해 문제의 한 조각만을 해결하고 나머지를 재귀 호출로 해결하기로 하겠음. 

1. i번 상자를 사지 않는 경우 : 이 상자를 제외하고 나머지 상자들에 대해 재귀 호출로 문제를 해결함. 따라서 이 경우의 답은 maxBuys(i-1)이 됨.

2. i번 상자를 사는 경우: 만약 j로 선택할 수 있는 상자가 여러 개 있을 수 있다면 그중 가장 뒤에 있는 상자를 구입해야만 이득임. 우리의 목적은 가능한 한 많은 상자를 사는 것이 아니라 구간의 수를 최대화하는 것이기 때문임. j를 선택한 경우의 답은 maxBuys(j-1)+1이 됨.