[C++][백준][알고리즘] 약수 🎯

1037번

1037번: 약수

• 양수 A는 진짜약수(1과 자기 자신을 제외)한 값 중에서 최소값과 최대값을 서로 곱하면 자기 자신이 나옵니다.

 

17427번

17427번: 약수의 합 2

 

틀린 코드

#include <iostream>
#include <climits>
#include <cmath>

using namespace std;

int main() {
	int N;
	int answer = 0;
	scanf("%d", &N);
	
	for(int i = 1; i <= N; ++i)
	    for(int j = 1; j <= sqrt(i); ++j)
	        if(i % j == 0)
	        {
	            int temp = i / j;
	            if(temp != j)
	                answer += temp;
	        
	            answer += j;
	        }

    printf("%d", answer);
	return 0;
}

• sqrt를 사용하여 n *  √n으로 계산할 수 있습니다. 하지만 이 방법은 제한 시간 0.5초를 벗어난 크기입니다.
• 1,000,000 * 1,000은 1,000,000,000(10억)으로, 10초정도 소요되는 풀이 방법으로 해결할 수 없습니다.

 

맞은 코드

#include <iostream>
#include <climits>
#include <cmath>

using namespace std;

int main() {
	int N;
	long long answer = 0; // 수는 매우 커질 수 있기에 long long int로 선언
	scanf("%d", &N);
	
	/*
	    N이하 자연수 중 3을 약수로 갖는 수의 개수는 N / 3개!
	    그 이유는, 3의 배수로 이루어진 수는 N으로 나누어 떨어질 때 무조건 
	    그 수를 약수로 포함하기 때문!
	    
	    N이하의 자연수 중에서 1을 약수로 갖는 수의 개수는 ⌊N/1⌋개
        N이하의 자연수 중에서 2를 약수로 갖는 수의 개수는 ⌊N/2⌋개
        N이하의 자연수 중에서 3을 약수로 갖는 수의 개수는 ⌊N/3⌋개
        ...
        N이하의 자연수 중에서 i를 약수로 갖는 수의 개수는 ⌊N/i⌋개
	*/
	for(int i = 1; i <= N; ++i)
	{
	    int cnt = N / i;
	    answer += cnt * i;
	}

    // lld: long long int 출력
    printf("%lld", answer);
	return 0;
}

• 배수를 활용한 방식으로 문제를 해결하였습니다.
• N이하의 자연수 중에서 1을 약수로 갖는 수의 개수는 ⌊N/1⌋개로 볼 수 있습니다. 그 이유는 1의 배수로 이루어진 수는 해당 수가 모두 1을 약수로 가지기 때문입니다.
• 예를 들어 9 이하의 자연수 중 3을 약수로 가지는 개수는 9/3으로 계산하여 3이 나옵니다.
  • 3, 6, 9는 3의 배수이며, 이 수들은 모두 3을 약수로 가지게 됩니다.
• 이런 방식으로 접근하여 1~N까지의 모든 약수의 합을 구하려면 N번 반복하면 문제를 해결할 수 있습니다.

 

17425번

17425번: 약수의 합

#include <iostream>
#include <vector>
using namespace std;

const int MAX = 1000000;

int main() {
    vector<long long> dp(MAX + 1, 1);
    vector<long long> s(MAX + 1, 0);
    
    // 인덱스 번호에 해당하는 배수를 누적하여 저장
    // i의 배수가 가리키는 값은 i를 항상 약수로 가지는 성질
    for (int i = 2; i <= MAX; ++i) 
        for (int j = 1; i * j <= MAX; ++j) 
            dp[i * j] += i;

    // 인덱스 번호의 약수 합을 누적하여 차례대로 저장
    for (int i = 1; i <= MAX; ++i)
        s[i] = s[i - 1] + dp[i];

    int T, N;
    scanf("%d", &T);
    
    for(int i = 0; i < T; ++i)
    {
        scanf("%d", &N);
        printf("%lld\n", s[N]);
    }

    return 0;
}

• 17427번과 같은 문제이지만, 테스트케이스가 추가되어 각 테스트케이스를 각각 구하게 된다면 시간초과하는 문제입니다.
• 이 문제는 dp를 이용하여 MAX까지의 값을 일단 구하고, g(n)을 s라는 벡터에 미리 저장하여 모든 테스트 케이스에 대비하여 출력을 마지막에 하는 방식으로 해결하였습니다.