[BOJ] 백준_17427번_약수의 합 2_C/C++백준 알고리즘2021. 9. 17. 10:32
목차
문제 출처
https://www.acmicpc.net/problem/17427
문제
두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더한 값이고, f(A)로 표현한다. x보다 작거나 같은 모든 자연수 y의 f(y)값을 더한 값은 g(x)로 표현한다.
자연수 N이 주어졌을 때, g(N)을 구해보자.
입력
첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.
출력
첫째 줄에 g(N)를 출력한다.
시간 초과 코드
//[BOJ] 17427번_약수의 합 2_시간 초과
#include <iostream>
using namespace std;
int main()
{
int N;
long long tot = 0;
cin >> N;
if ((N < 1) || (N > 1000000)) {
cout << "N의 범위를 벗어났습니다." << endl;
exit(1);
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= i; j++) {
if (i % j == 0) {
tot += j;
}
}
}
cout << tot << endl;
return 0;
}
코드
//[BOJ] 17427번_약수의 합 2
#include <iostream>
using namespace std;
int main()
{
int N;
long long tot = 0;
cin >> N;
if ((N < 1) || (N > 1000000)) {
cout << "N의 범위를 벗어났습니다." << endl;
exit(1);
}
for (int i = 1; i <= N; i++)
tot += (N / i) * i;
cout << tot << endl;
return 0;
}
고민없이 쭉 풀리는 문제였다. 컴파일러에서는 문제가 없지만 백준에서 채점을 할 때에는 자연수 N의 범위가 1,000,000까지이기 때문에 약수의 총합을 담는 tot의 자료형을 int로 선언했을 경우 오류 메세지가 뜰 것이다. 그렇기 때문에 tot의 자료형을 long long으로 선언해줘야 한다는 것에 주의를 기울였다. 또한 약수를 추출해 담는 과정에서도 마찬가지로 1부터 i까지 차례로 나눠보고 체크하는 코드는 시간 초과가 발생했다. 그래서 새로운 규칙을 찾아야 했는데 N의 약수가 i라면 i의 개수가 N/i개 라는 규칙이 있었다. 때문에 (N/i)*i를 차례로 더해서 tot에 담았다.
728x90
반응형
LIST
'백준 알고리즘' 카테고리의 다른 글
[BOJ] 백준_10972번_다음 순열_C/C++ (0) | 2021.09.22 |
---|---|
[BOJ] 백준_1008번_A/B_C/C++ (0) | 2021.09.18 |
[BOJ] 백준_1037번_약수 / C, C++ (0) | 2021.09.16 |
[BOJ] 백준_1748번_수 이어 쓰기1 / C언어, C++ (0) | 2021.09.15 |
[BOJ] 백준_1476번_날짜 계산 / C++ (0) | 2021.09.14 |
@kdj :: Childev'note
포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!