오답노트
[수학] BOJ17427 약수의 합 2 - 오답노트 본문
https://www.acmicpc.net/problem/17427
- 문제 파악
자연수 N이 주어지면 1부터 N까지 각 자연수 마다 약수의 합을 모두 더하는 문제
- 나의 시도
무식하게 1부터 약수 구하여 더하고 를 N까지 반복, 하지만 자료형은 신경써서 unsigned long long 으로 답을 도출 하였으나.. 결과는 시간 초과 log(N) 이 되도록 로직을 구성하려고 시도했다.
자연수 k의 배수는 자연수 k의 약수 + 자기 자신
이라는 아이디어로 접근하였으나, 공배수를 처리해야하는 모순에 도달했다.
- 정답
1부터 N까지 약수를 나열 해놓고 1부터 N까지 그 개수를 세어보면 아래와 같다.
1 : N/1 개
2 : N/2 개
3 : N/3 개
4 : N/4 개
.
.
.
N : N/N 개
위에서 극단적으로 봤을때 1은 모든 수의 약수가 됨으로 (자기 자신도) 1은 반드시 N개가 존재한다. 또 N은 1부터 N까지의 약수 중에 오로지 자기 자신만 존재하므로 1개가 존재한다. 그러므로 코드는 아래와 같다.
#include "bits/stdc++.h"
using namespace std;
int main()
{
int n;
cin>>n;
unsigned long long ans = 0;
for(int i = 1 ; i <= n ; i++ )
{
unsigned long long tmp = n/i; // i의 개수
ans += (i * tmp);
}
cout<<ans;
}
- 느낀점
관찰력이 매우 부족했다. 단 몇줄이면 끝날것을 몇십줄로 만들다니.. 조금 더 면밀하게 패턴을 파악해보자
'C,C++ > 코딩테스트' 카테고리의 다른 글
[수학] BOJ 2960 에라토스테네스의 체 (0) | 2022.04.24 |
---|---|
[수학][DP] BOJ 17425 약수의 합 - 오답노트 (0) | 2022.04.21 |
DP 점화식 패턴 (0) | 2022.04.13 |
수학 관련 팁 (0) | 2022.03.23 |
BFS 관련 팁 (0) | 2022.03.17 |