[백준] 17427번 약수의 합2 (C++)

문제

https://www.acmicpc.net/problem/17427

17427번: 약수의 합 2

코드

첫 번째 시도(시간 초과)

#include <iostream>

using namespace std;

int main(){
  int n;
  int result = 0;
  cin >> n;
  for(int i=1; i<=n; i++){
    for(int j=1; j<=i; j++){
      if(i%j==0) result+=j;
    }
  }
  cout << result;
  return 0;
}

 

solution

#include <iostream>

using namespace std;

int main(){
  int n;
  cin >> n;
  long long result = 0;
  for(int i=1; i<=n; i++){
    result+=(n/i)*i;
  }
  cout << result;
  return 0;
}

정리

처음에는 직관적으로 이중for문을 사용하여 문제를 풀었으나 역시나 시간초과가 나왔다.

n을 10으로 하고 한 번 나열해보았더니 규칙이 보였다. 다음 표를 봐보자

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번

2 → 5번

3 → 3번

4 → 2번

5 → 2번

6 → 1번

7 → 1번

8 → 1번

9 → 1번

10 → 1번

따라서 총 약수의 합을 1*10+2*5+3*3+4*2+5*2+6*1+7*1+8*1+9*1+10*1=87로 구할 수 있다.

이것은 1부터 n까지 n을 i로 나눈 몫에 i를 곱한 수들의 합으로 표현할 수 있다.

참조

https://kangeee.tistory.com/138