[BOJ C++] 백준 16488번: 피카츄가 낸 어려운 문제

 📚 문제

[BOJ C++] 백준 16488번: 피카츄가 낸 어려운 문제
https://www.acmicpc.net/problem/16488

 

---

 📝 입력 및 출력

 

---

 🔎 문제 풀이

• 기하 문제이다. 피타고라스 정리와 시그마를 이용하면 식을 구할 수 있다. 계산 과정은 다음과 같다.

• 선분 BC의 길이를 $a$, 삼각형의 높이를 $h$라고 할 때, 위 그림과 같이 각 길이를 나타낼 수 있다.
• 피타고라스 정리를 이용하여 $h$와 $\overline{AP_i}^2$를 나타낼 수 있다.$\overline{P_iP_\frac{K}{2}}=\overline{BP_\frac{K}{2}}-\overline{BP_i}=\frac{a}{2}-\frac{ia}{K+1}$$=N^2-\frac{a^2}{4}+\frac{a^2}{4}-\frac{ia^2}{K+1}+\frac{i^2a^2}{(K+1)^2}=N^2-\frac{ia^2}{K+1}+\frac{i^2a^2}{(K+1)^2}$
• $= N^2+\frac{i^2a^2-(K+1)ia^2}{(K+1)^2} = N^2+\frac{ia^2(i-K-1)}{(K+1)^2}$
• $\overline{AP_i}^2=\overline{AP_\frac{K}{2}}^2+\overline{P_iP_\frac{K}{2}}^2=h^2+(\frac{a}{2}-\frac{ia}{K+1})^2$
• $h^2=\overline{AP_\frac{K}{2}}^2=\overline {AB}^2-\overline{BP_\frac{K}{2}}^2 = \sqrt{N^2-\frac{a^2}{4}}$
• 앞서 나타낸 식으로 $\overline{BP_i}\times \overline{CP_i}$를 나타낼 수 있다.이를 바탕으로 $F(i) = \overline{AP_i}^2 + \overline{BP_i}\times \overline{CP_i}$를 계산해보면,이때, i값은 1부터 k까지 변화하므로 $\displaystyle\sum_{i=1}^{k} F(i) = \displaystyle\sum_{i=1}^{k} N^2 = N^2 \times K$이다.
• 즉, 입력받은 N과 K에 대해 $N^2 \times K$ 값을 출력하면 된다.
• $N^2+\frac{ia^2(i-K-1)}{(K+1)^2} + \frac{ia^2(K+1-i)}{(K+1)^2} = N^2$ 이 되는 것을 알 수 있다.
• $\overline{BP_i}\times \overline{CP_i} = \frac{ia}{K+1} \times \frac{(K+1-i)a}{K+1}=\frac{ia^2(K+1-i)}{(K+1)^2}$

• N과 K가 100,000 이하의 양의 정수이므로 결과값은 int 범위를 넘어간다. 즉, 형변환이 필요하다.

---

 ⌨️ C++ 코드

#include <bits/stdc++.h>
using namespace std;

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, k;
    cin >> n >> k;
    cout << (long long) n * n * k; // 형변환 주의.
}

코드로 구현하는 것보다 식을 도출해내는 것이 더 어려운 문제였다...