[BOJ 23848] 백준 23848번 - 등비수열의 합
| INU 코드페스티벌 2021 풀이 | ||
|---|---|---|
| A | [BOJ 23841] 데칼코마니 | |
| B | [BOJ 23842] 성냥개비 | |
| C | [BOJ 23843] 콘센트 | |
| D | [BOJ 23844] 트리 정리하기 | |
| E | [BOJ 23845] 마트료시카 | |
| G | [BOJ 23847] INU 막대기 | |
| H | [BOJ 23848] 등비수열의 합 |
1. 문제
$23848$. 등비수열의 합 (INU 코드페스티벌 2021 Open Contest H번)
2. 풀이
항이 세 개 이상이고 $N$의 최댓값이 $10^{12}$이므로, 공비의 최댓값은 $10^6$ 정도로 생각할 수 있다. $(1$ $+\;1,000,000$ $+\;1,000,000,000,000$ $=1,000,001,000,001)$
또한, $a\times (r^n-1)/(r-1)=N$에서 $a=1, r=2$로 가정하면, $2^n-1=10^{12}$이므로 항의 개수의 최댓값은 $40$ 정도로 생각할 수 있다.
각각의 공비$(2\sim 1,000,000)$에 대해서 항의 개수$(3\sim 40)$만큼 돌리면 대략 $40,000,000$ 정도의 시간복잡도가 나오고 이는 시간 안에 돌리기 충분하므로 이런 식으로 브루트포스 알고리즘을 구현하면 된다.
임의의 공비 $r$과 항의 개수 $n$에 대해서, 등비수열 합 공식을 변형하여 $N\times (r-1)\%(tmp-1)$이 $0$인지 확인해서 자연수 $a$를 구할 수 있는지 체크한다. (이때, 거듭제곱의 시간복잡도를 최소화하기 위해 변수 하나에 누적곱을 하는 방식으로 구현하였다.)
단, 주의해야할 점이 하나 있다. long long int의 범위는 대략 $10^{18}$까지이다. 따라서 범위를 넘어버려서 오버플로우가 발생하는 일은 없도록 해야 한다. 나는 누적곱이 $10^{12}$를 넘어가면 break를 거는 방식으로 구현하였다.
3. 채점 결과
4. 회고
처음에는 접근방식 자체가 틀려서 WA를 받았다. 나중에는 공비가 $10^{12}$의 세제곱근인 $10,000$으로 충분할 줄 알고 해당 범위로 구현해버려서 WA를 받았다.
댓글남기기