[BOJ 23828] 백준 23828번 - 수열 (Hard)
1. 문제
$23828$. 수열 (Hard) (SASA Programming Contest 2021 Open Contest C2번)
백준 23828번 - 수열 (Hard) (https://www.acmicpc.net/problem/23828)
2. 풀이
수열이 $[3,1,1,2,2,2]$, $M=2$라고 가정해보자. 그러면 다음과 같이 된다. $A(b1)\times a(b2)\times …\times A(bm)의 합 $ $= (3\times 1+3\times 1+3\times 2+3\times 2+3\times 2)$ $+\;(1\times 2+1\times 2+1\times 2)$ $+\;(1\times 2+1\times 2+1\times 2)$
$3\times 1$이 $(3의 개수)\times (1의 개수)$만큼 있고, $3\times 2$가 $(3의 개수)\times (2의 개수)$만큼 있고, $1\times 2$가 $(1의 개수)\times (2의 개수)$만큼 있는 셈이다. 이를 정리하면 다음과 같다. $(3\times 1\times 1\times 2)$ $+\;(3\times 2\times 1\times 3)$ $+\;(1\times 2\times 2\times 3)$$
그런데 $1\times 2\times 2\times 3$에서 $(1\times 2)$가 $(1의\;개수)\times(2의\;개수)$만큼 있는 것이 아니라, 교환법칙에 의해서 $(1\times (1의 개수))\times (2\times (2의개수))$ 이렇게 바꿔서 생각할 수 있다.
$(3\times 1\times 1\times 2)$ $+\;(3\times 2\times 1\times 3)$ $+\;(1\times 2\times 2\times 3)=((3\times 1)\times (1\times 2)) $ $+\;((3\times 1)\times (2\times 3))$ $+\;((1\times 2)\times (2\times 3))$ $=(3\times 2)$ $+\;(3\times 6)$ $+\;(2\times 6)$
이는 수열 $[3,2,6]$, $M=2$인 경우와 동일한 값이 된다. 따라서, 중복되는 수들은 전부 합하여 하나의 수로 정의할 수 있다는 의미가 된다. (모든 $M$에 대해 동일)
위의 추론에 따라서, 순서와 상관없이 중복되는 수들을 모두 한데 모아 합하여 하나의 수로 가정해서 새로운 길이$(N’)$의 수열을 만든다.
나는 수열을 정렬하여 연속되는 같은 수들을 합하는 방법을 사용했지만, $A(i)$가 $100,000$미만이므로 $100,000$길이의 cnt배열을 정의하여 직접 수를 하나씩 체크하며 개수+1을 해주고 나중에 하나의 수로 만드는 방법이 더 쉬울 것이다.
이 새로운 수열을 만들고 나면 이제 길이$(N’)$의 수열에서 $M$개를 고른 모든 $A(1)\times A(2)\times …\times A(M)$의 합을 구하면 된다.
$M-1$개만큼 고른 합이 $M$개만큼 고른 합에 영향을 주므로 dp(dynamic programming)를 생각해볼 수 있다. dp[i][j]를 $A(i)$까지 $j$개를 골라서 만든 합으로 가정한다. 이전단계 dp[i-1][?]에서 수 $A(i)$가 추가된다고 생각해보면, 수 $A(i)$를 고를 것인지 고르지 않을 것인지 두 가지 경우의 수로 나뉜다.
- 수 $A(i)$를 고르는 경우 -> 추가된 수에 대해서 다른 모든 $j-1$개를 고른 경우와의 곱을 계산해야 한다. $\rightarrow$ $dp[i][j] = dp[i][j]$ $ + dp[i-1][j-1] \times A(i)$
- 수 $A(i)$를 고르지 않는 경우 $\rightarrow$ 이미 $j$개를 고른 경우가 계산되어 있다. $\rightarrow$ $dp[i][j] = dp[i][j] + dp[i-1][j]$
따라서 $dp[i][j] = dp[i-1][j-1] \times A(i)$ $ +\; dp[i-1][j]$ 이다. (나는 코드 51줄에서 $v[i]$가 아니라 $v[i-1]$로 되어 있는데, 이는 $v$의 index만 $0$으로 시작하게 만들어 버려서 그렇다.)
3. 채점 결과
4. 회고
.
댓글남기기