문제
https://www.acmicpc.net/problem/9546
n명의 승객을 태우고 있는 3000번 버스는 버스 정류장마다 문을 연다. 정류장마다 타고 있는 승개의 수의 절반과 반 명의 승객이 내린다. k개의 정류장에서 승객이 내렸고, 마지막 정류장에서 승객이 없었다면 맨 처음 타고 있던 승객이 몇 명인지 구하여라.
풀이
t번째 정류장에서의 승객의 수를 \( n_t \)라고 하자.
정류장마다 내리고 남은 승객의 수는 아래와 같이 계산할 수 있다.
$$ \begin{matrix} n_t - (0.5n_t + 0.5) = n_{t+1} \\ 0.5n_t - 0.5 = n_{t+1} \end{matrix} $$
마지막 정류장에서의 승객이 0명이므로, 정류장이 1개인 경우, 2개인 경우, 3개인 경우……를 순서대로 계산하면 아래와 같다.
| 정류장 수(k) | 남은 승객 수 | 타고 있던 승객 수 |
| 1 | \( 0.5n_t - 0.5 = 0 \) | 1 |
| 2 | \( 0.5n_t - 0.5 = 1 \) | 3 |
| 3 | \( 0.5n_t - 0.5 = 3 \) | 7 |
| 4 | \( 0.5n_t - 0.5 = 7 \) | 15 |
타고 있던 승객 수는 1, 3, 7, 15…… 로 증가하는데, 그 증가량이 2, 4, 8……인 것을 알 수 있다. 조금 더 풀어쓰면 아래와 같이 표현할 수 있다.
| 정류장 수(k) | 타고 있던 승객 수 |
| 1 | 1 = 1 |
| 2 | 3 = 1 + 2 |
| 3 | 7 = 1 + 2 + 4 |
| 4 | 15 = 1 + 2 + 4 + 8 |
즉, k개의 정류장을 지나기 위해 처음 타고 있던 승객의 수는 초항이 1이고 공비가 2인 등비수열의 합에 해당한다.
초항이 a이고 공비가 r인 등비수열의 합 공식은 아래와 같다. 대입하여 풀어보자.
$$ \begin{matrix} S_k &=& \frac{a(r^k - 1)}{(r - 1)} &=& \frac{1(2^k - 1)}{(2 - 1)} \\ &=& 2^k - 1 \end{matrix} $$
결론
k개의 정류장을 지나기 위해 처음 타고 있던 승객의 수는 \( 2^k - 1 \)이다.
코드
풀이를 토대로 코드를 작성하면 아래와 같다.
import sys
n = int(sys.stdin.readline())
for _ in range(n):
k = int(sys.stdin.readline())
print(2 ** k - 1)
참고 문서
https://ko.wikipedia.org/wiki/%EB%93%B1%EB%B9%84%EC%88%98%EC%97%B4