(JAVA) 백준 15284번 : 너 봄에는 캡사이신이 맛있겠다 --- [수학, 조합, 정렬]

www.acmicpc.net/problem/15824

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

 

안녕하세요.

 

이 문제는 수학 + 조합 + 정렬 입니다.

그리고, solved.ac 기준 골드1 문제입니다.

 

처음 시간 초과가 발생했었는데,

 

정렬(O(n)) -> 두 지점을 잡고(O(n^2)) -> 각 지점 내의 원소로 만들 수 있는 조합 개수(DP로 미리 구해둠.) * (높은 지점 - 낮은지점) 

 

대충 이런 매커니즘으로 작성했었고, 당연히 1초 시간제한인 이 문제에서는 통과를 못했었습니다.

 

 

결국, 몇 번 풀이를 참고해서 이해했습니다.

아직 제대로 푸는 문제가 별로 없네요..ㅎㅎ

 

 

 

이 문제는 결국

오름차순으로 정렬되어있는 배열이라고 가정했을 때,

 

최대가 될 수 있는 조합의 모든 경우의 수 * 그 때의 최댓값 - 최소가 될 수 있는 조합의 모든 경우의 수 * 그 때의 최솟값 을 구하면 됩니다.

 

 

 

 

즉, 

1 ~ n 까지 n개의 오름차순 정렬이 되어있는 배열이 있을 때,

 

전체를 한 번 for문 순회하면서

 

i번 째 인덱스(i라고 하자.) 의 경우

i-1번 째 부터 1번 째 까지는 i번 째 값보다 무조건 작고,

i+1번 째 부터 n번 째 까지는 i번 째 값보다 무조건 큽니다.

 

 

이에 더해, 모든 경우의 수를 구하는 방법은

 

i-1 ~ 1번 째까지 (또는 i+1 ~ n번 째까지) 조합의 경우를 각각 포함하는 / 포함하지 않는 2가지 경우가 존재하므로 

전체 조합의 경우의 수는 2^(i-1) (또는 2^(n-i)) 가 나올 수 있습니다.

 

 

그렇게 된다면 결국

 

전체 경우의 수 = (2^(i-1) * arr[i])  - (2^(n-i) * arr[i]) = (2^(i-1) - 2^(n-i)) * arr[i] 

*** (i번 째의 값이 최대가 될 때, 모든 조합으로 나올 수 있는 최댓값) - (i번 째의 값이 최소가 될 때, 모든 조합으로 나올 수 있는 최솟값)

 

 

입니다.

 

 

 

좀 더 자세한 매커니즘은 아래 소스코드를 참고해주세요.

궁금하신 사항이 있으면 댓글 부탁드립니다.

 

감사합니다!

 

 

소스코드

---