백준 15824 - 너 봄에는 캡사이신이 맛있단다

https://www.acmicpc.net/problem/15824

15824번: 너 봄에는 캡사이신이 맛있단다

예제 출력을 이해하는 데만 한참 걸렸다.

 

0. '메뉴의 조합'이란 크기 2부터 N까지, 즉 서로 다른 최댓값과 최솟값을 갖는 조합을 의미하는 듯 하다. 사실크기가 1인 조합도 존재하지만 최댓값과 최솟값이 같으므로 주헌고통지수가 0이 되어 합에 영향을 주지 않는다.

 

그래서 메뉴가 5,2,8 3가지가 있으면 (2,5), (2,8), (5,8), (2,5,8) 4개의 조합이 가능하며 각각의 주헌고통지수는 3,6,3,6으로 출력값에 이들의 총합에 해당하는 18이 나온다.

 

그렇다면 모든 조합을 일일히 찾는 브루트포스 알고리즘을 활용해야 하는가? 문제의 요구사항이 최댓값과 최솟값이기 때문에 그럴 걱정은 하지 않아도 된다.

 

1. 이렇게 생각해보자.

예제 입력 1에서, 2를 최솟값으로 갖는 조합은 총 몇 개인가? 어떤 조합이 2를 최솟값으로 가지기 위해서는, 원소 2는 반드시 가져야하며 2보다 큰 원소들 중 최소 하나 이상은 가져야 한다. 따라서 조합의 수는 2보다 큰 원소들 5, 8 중 최소 하나 이상을 선택하는 경우의 수가 될 것이다.

 

원소가 n개인 집합의 부분집합의 수는 2^n이며, 최소 하나 이상은 가져야 하므로 공집합을 제외한 총 2^n - 1개의 부분집합이 존재한다. 따라서 최솟값이 2인 조합의 개수는 2^2 - 1 = 3개이다.

최솟값이 5인 조합은? 8에서 하나를 선택하므로 2^1 - 1 = 1개.

8인 조합은? 2^0 - 1 = 0개.

 

2. 이를 일반화해보자.

먼저 매번 원소의 크기를 비교하기보다는 배열을 정렬한다. 크기 n의 배열 v에 대해, 최솟값이 v[0]인 조합의 개수는 나머지 n-1개 원소들 중 최소 하나를 고르는 경우의 수로 2^(n-1) - 1이다.

 

i번째 원소에 대해, 최솟값이 v[i]인 조합의 개수는 v[i]보다 큰 n-i-1개 원소들 중 하나를 고르는 경우의 수로 2^(n-i-1) - 1이다. 최댓값도 마찬가지로, 최댓값이 v[i]인 조합의 개수는 v[i]보다 작은 i개 원소들 중 하나를 고르는 경우의 수로 2^i - 1이다.

 

주헌고통지수의 총합 = 모든 조합의 최댓값의 합 - 모든 조합의 최솟값의 합이므로 v[i] * (2^i - 1) - v[i] * (2^(n-i-1) - 1) = v[i] * (2^i - 2^(n-i-1)) (0 <= i < n) 의 합을 계산하면 문제의 답을 구할 수 있다.

 

이제 분할 제곱과 나머지 정리를 적절히 활용하면 된다.

 

3. 내가 문제를 풀며 어려움을 겪은 부분은, 2^i - 2^(n-i-1)이 음수가 되는 경우를 처리하는 것이였다.

반복문을 i=n-1에서부터 수행하면, v[i]가 큰 값을 가지며 2^i - 2^(n-i-1)는 i = n/2까지 양수이므로 합이 음수가 될 일은 없겠다고 생각했지만 자꾸 틀렸습니다가 떴다.

 

그 이유는 2^k에 나머지 연산이 포함되었기 때문이다.

(2^3 - 2^1) % 7은 양수지만, (2^3 % 7 - 2^1 % 7) % 7은 음수이다. 합이 언제 음수가 될 지 모르니 매 연산마다 음수 처리를 따로 해주어야한다.

while(sum < 0) sum += m;