[백준 BOJ] 17427번 - 약수의 합 2

📌 참고

교공 알고리즘 스터디에서 다룬 문제는 19주차부터 벨로그에 기록하고 있습니다 (18주차 이전 문제들을 추후 복습 겸 업로드할 계획도 있습니다 🤗) 그 외 개인적으로 풀어본 백준 및 프로그래머스 문제는 스스로 유의미하다고 여겨진 부분들이 있는 문제만 선별하여 벨로그에 기록하고 있습니다 벨로그에 올라오지 않은 다른 문제와 코드가 궁금하신 분들은 아래의 github에서 추가로 확인하실 수 있습니다 👀 방문해주셔서 감사합니다 🙏

💚 github | dianstar/Algorithm-BOJ
💚 github | dianestar/Algorithm-Programmers

code.plus 문제집 : 코딩 테스트 준비 - 기초 | 수학

17427번: 약수의 합 2 | 문제 바로가기

문제풀이 (2022-02-02 WED 💻)

⭐ 풀이의 핵심

자연수 A의 약수의 합은 A의 모든 약수를 더한 값이고, f(A)로 표현한다.
x보다 작거나 같은 모든 자연수 y의 f(y)값을 더한 값은 g(x)로 표현한다.

👉 위와 같이 문제에 제시된 f(A)와 g(X)를 하나하나 그대로 구현하면
(즉, 1부터 N까지 각각 f(A)를 다 구하고 이 값들을 더해주는 과정을 거치면)
시간초과가 발생한다

안그래도 제한 시간이 0.5초라 시간 관리를 잘 해야하는 문제라는 건 눈치 챘지만
결과가 궁금해서 (?) 그대로 구현해보았고 (아래 코드에 주석 처리된 부분)
아니나 다를까 시간초과가 떴다

따라서 아래와 같이 애초에 g(x) 값에서 찾을 수 있는 패턴 을 통해 답을 구해야 한다

ex)
1의 약수  : 1
2의 약수  : 1 2
3의 약수  : 1   3
4의 약수  : 1 2   4
5의 약수  : 1       5
6의 약수  : 1 2 3    6
7의 약수  : 1           7
8의 약수  : 1 2   4     8
9의 약수  : 1   3         9
10의 약수 : 1 2   5      10

---

총합
1*(10/1) + 2*(10/2) + 3*(10/3) + 4*(10/4) + 5*(10/5) + 6*(10/6) + 7*(10/7) + 8*(10/8) + 9*(10/9) + 10*(10/10)
= 1*10 + 2*5 + 3*3 + 4*2 + 5*2 + 6*1 + 7*1 + 8*1 + 9*1 + 10*1
= 87

👉 시간 뿐만 아니라 변수의 자료형 범위 도 잘 생각해줘야 하는 문제이다

N이 최댓값인 1,000,000일 경우 answer의 값은 822,468,118,437로
int의 범위인 -2,147,483,648~2,147,483,647을 초과 한다
(대충 21억 또는 10자리수를 넘기면 int 범위를 넘어간다고 생각 해주면 된다)

따라서 answer 변수를 int가 아니라 long long으로 선언 해주어야 한다

🚨 간과 또는 실수한 부분

위의 풀이의 핵심에서 설명한 것처럼 answer 변수는 long long으로 잘 선언해두고
출력 포맷을 "%lld" 가 아니라 "%d"로 해놔서 틀렸습니다 가 떴다..
어제에 이어서 또 출력 포맷 실수.. 실수도 실력이다 😥
🔥 마음 급하게 먹지 말고 끝까지 꼼꼼히 풀자!

🔽 코드 (C++)

#include <iostream>
using namespace std;

int main() {
    int N;
    scanf("%d", &N);

    long long answer = 0;
    for (int i=1; i<=N; i++) {
        answer += i*(N/i);
    }
    printf("%lld", answer);

    return 0;
}

/*
시간 초과 발생 코드

int f(int num) {
    int sum = 0;
    int squareRoot = (int)sqrt(num);
    for (int i=1; i<=squareRoot; i++) {
        if (num % i == 0) {
            sum += i;
            if (i*i != num) {
                sum += num / i;
            }
        }
    }
    return sum;
}

int main() {
    int N;
    scanf("%d", &N);

    int answer = 0;
    for (int i=1; i<=N; i++) {
        answer += f(i);
    }
    printf("%d", answer);

    return 0;
}
*/