특정 규칙에 의해 살아야 하는 아파트의 k층 n호에 살려면 몇 명이 살아야 하는지 구하는 문제입니다. 이 문제는 푸는 방법이 두 가지가 있을 것 같습니다.
첫 번째는 2차원 배열을 이용하여 푸는 방법입니다. k와 n은 14 이하이고 0층부터 시작하므로 15*14 크기의 2차원 배열을 선언합니다. 그리고 0층에 해당하는 행에 1부터 14까지 집어넣은 후 반복문을 이용하여 규칙에 맞게 나머지 칸을 채워나가는 방법입니다. 테스트케이스가 여러 개이므로 이 배열을 한 번 채운 후 다른 케이스를 풀기 위해 다시 계산할 필요가 없고 원하는 위치에서 값을 꺼내면 됩니다. 일종의 DP라고 볼 수 있죠.
두 번째는 수식을 이용한 방법입니다. 먼저 0층은 i호에 i명이 산다는 조건이 있습니다. 그렇다면 1층의 i호에는 0층의 1호부터 i호까지 사람 수의 합인 \(\frac{i(i+1)}{2}\)이 될 것입니다. 이제 2층을 구할 것인데, 2층은 \(\frac{i(i+1)}{2}\)의 합입니다. 1부터 i2까지의 제곱의 합을 구하는 공식인 \(\frac{n(n+1)(2n+1)}{6}\)을 사용해보면 2층의 i호에 사는 사람은 \(\frac{i(i+1)(i+2)}{6}\)가 됩니다. 마찬가지로 3층을 구해보면 \(\frac{i(i+1)(i+2)(i+3)}{24}\)가 됩니다. 규칙이 보이나요? 일반식은 k층 n호일 때 \(\frac{(n+k)!}{(n-1)!(k+1)!}\)입니다. 식을 조금 다르게 쓰면 \(\frac{n}{1}\times\frac{n+1}{2}\times\frac{n+2}{3}\times...\times\frac{n+k-1}{k}\)가 되므로 반복문을 이용하여 쉽게 구할 수 있습니다.
증명
$$
\text{Define } S_k(n)=\sum_{i=1}^{n}S_{k-1}(i)=S_{k-1}(n)+S_{k}(n-1),S_0(n)=n,S_k(1)=1\\
\text{Assume } S_k(n)=\frac{(n+k)!}{(n-1)!(k+1)!}\\
k=0\Rightarrow S_0(n)=n=\frac{(n+0)!}{(n-1)!1!}:\text{성립}\\
k=1\Rightarrow S_1(n)=\frac{n(n+1)}{2}=\frac{(n+1)!}{(n-1)!2!}:\text{성립}\\
n=0\Rightarrow S_k(0)=0=\frac{k!}{(-1)!(k+1)!}:\text{성립}\\
n=1\Rightarrow S_k(1)=1=\frac{(k+1)!}{0!(k+1)!}:\text{성립}\\
\begin{align*}
S_{k}(n)&
=S_{k-1}(n)+S_{k}(n-1)\\
&=\frac{(n+k-1)!}{(n-1)!k!}+\frac{(n+k-1)!}{(n-2)!(k+1)!}\\
&=(n+k-1)!(\frac{1}{(n-1)!k!}+\frac{1}{(n-2)!(k+1)!})\\
&=\frac{(n+k-1)!}{(n-1)!(k+1)!}((k+1)+(n-1))\\
&=\frac{(n+k-1)!(n+k)}{(n-1)!(k+1)!}\\
&=\frac{(n+k)!}{(n-1)!(k+1)!}
\end{align*}\\
\therefore S_{k}(n)=\frac{(n+k)!}{(n-1)!(k+1)!}
$$
따라서 k층 n호에 사는 사람 수는 위 식을 통해 구할 수 있겠습니다.
소스 코드
| 언어 | 코드 | 시간 |
|---|---|---|
| Python 3 | 코드(Github) / 코드(백준) | 2020-03-26 14:56:24 |