https://www.acmicpc.net/problem/23828
문제요약
- 주어진 수열에서 서로 다른 M개를 고름(N = 1000,숫자 = 10만)
- M개의 숫자는 서로 달라야함
- 고른 숫자를 곱하고, 나올 수 있는 모든 경우에 대해서 모두 더한 값 구하기(물론 MOD 연산)
접근법
- 많이 어려웠음. 어려웠던 것에 비해 티어가 매우 낮음
- 일단 중복 처리를 해야한다는 것은 알겠음
- 어떤 "선택"을 했으면 그 선택이 나올 수 있는 경우의 수는 모든 빈도수를 곱한 값임
- 예를들어 (1, 10개) (2, 3개), (7, 1개), (19, 100개) 에서 3개를 고를때
- (1, 2, 7)을 골랐다고 하면
- (1, 2, 7)은 10개 x 3개 x 1개 만큼 나타날 것임
- 즉 1 x 2 x 7은 10 x 3 x 1만큼 더해짐
- 즉 (1 x 2 x 7) x (10 x 3 x 1) 만큼 합에 기여됨
- 이렇게 생각해볼 수 있음
- C = 숫자 * 빈도수
- (C1, C2, C3, ... Ck)에서 M개를 골라서 곱한것들의 합
- C1까지 선택했을때 1개, 2개, ... M개
- C2까지 선택했을때 1개, 2개, ... M개
- Ck까지 선택했을때 1개, 2개, ... M개
- DP로 접근
- (....) => 5개를 선택한 덩어리들이 모여있는 상황에서
- 각각에 Ck를 곱하면 6개가 됨
- 그리고 Ck를 선택하기 전에까지 구성했던 6개도 있을 것임
- 둘을 합치면 Ck까지 선택했을때의 6개를 구할 수 있음
구현 - dp[i][j] : i원소까지 선택했을때 j개를 만들었을때의 계산 결과(i 원소는 꼭 선택을 할 필요는 없지만 고려는 하는 것임)
- dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1] * Ci
후기
- 많이 어려웠음
- 이걸 식의 전개로 접근한다고 함???
- (x + C1)(x + C2) ... (x + Ck)의 특정 항의 계수
newbieski