어쨌든 공부하는 블로그

https://www.acmicpc.net/problem/14929 풀이출력값은 x1 * x2 + x1 * x3 + ... x1 * xn + x2 * x3 + x2 * x4 + ...x2 * xn ... x(n-1) * xn 이므로정리해서 x1(x2 + x3 + ... xn) + x2(x3 + x4 + ... xn) 와 같이 표현할 수 있다이때 xi부터 xn까지 하나하나 더하는 과정을 n번 반복하면 시간초과가 되기 때문에 누적합을 이용한다 제출 코드#include using namespace std;int arr[100001];int ps[100001];int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n; ..

https://www.acmicpc.net/problem/3474 풀이오른쪽 끝에 나오는 0의 개수는 10이 얼마나 곱해졌는가를 구하면 된다그렇다면 10이 얼마나 곱해졌는가는 2와 5가 몇 개 곱해졌는가를 구하면 된다이때 2가 곱해진 횟수와 5가 곱해진 횟수 중 더 작은 횟수가 10이 곱해진 횟수라고 보면 되는데, 2는 모든 짝수가 해당되므로 팩토리얼 연산에서는 무조건 5가 곱해진 횟수보다 많다 따라서 5가 곱해진 횟수를 세면 되는데, N!을 계산하기 위해 1부터 N까지 루프문을 돌며 5가 등장하는 횟수를 세면 시간초과가 된다(N의 최댓값이 10억이기 때문) N이 125라면, 1부터 125까지를 곱해주어야 한다. 1부터 125까지의 수 중에 5의 배수가 등장하는 횟수는 125를 5로 나누어 쉽게 구할 수..