알고리즘 코드카타. 약수의 합(2024-06-11)

문제 개요

요약 : 정수 n을 입력받고 n의 약수의 합을 구하기
 
이 문제를 보자마자 이전에 풀이한 '나머지가 1이되는 수 찾기'가 생각났다. 거기서 얻은 지식을 활용해 풀 수 있을것이다.
 

---

풀이과정)
 
어떤 정수 n의 약수는 대칭적 특성을 가지고있다는것을 배웠다.
36을 기준으로 
1,2,3,4,6,9,12,18,36이 약수이며
 
36의 제곱근인 6을 중심으로 대칭적이다.
 
1 X 36 
2 X 18
3 X 12
4 X 9
6 X 6
 
이 공식을 다음과 같이 변형하면 문제의 답이 될것이다.
 
1 + 36
2 + 18
3 + 12
4 + 9
그리고 중심인 제곱근은 하나이므로 6을 더해준다. 그럼 다음과 같은 수식이 완성된다
 
1 + 36 + 2 + 18 + 3 + 12 + 4 + 9 + 6 = 91
 
주의! : 6 + 6을 하는 실수를 해선 안된다. 6은 엄연히 약수중 하나일 뿐이다. 이와 대칭되는 숫자가 없고 그저 36의 제곱근이다.
 
이 문제를 어떻게 따져봐야 하느냐!
 
36의 제곱근인 6보다 작은 숫자 n들이 36과 나누어 떨어지는가? 그렇다면 36에서 n을 나눈 몫과 n을 더하고 그 결과에서 계속 합산한다. 나누어 떨어지지 않는 수는 무시한다.
 
36 / 1 = 36 ------------> 1 + 36 = 37
36 / 2 = 18 ------------> 37 + 2 + 18 = 57
36 / 3 = 12 ------------> 57 + 3 + 12 = 72
36 / 4 = 9 ------------> 72 + 4 + 9 = 85
36 / 5 = 나누어 떨어지지 않으므로 무시한다.
제곱근인 6을 더해준다 ------------> 85 + 6 = 91
 
하지만 문제가 하나 더 남았다. 소수 또는 제곱근이 딱 떨어지지 않을 경우이다.
 
먼저 소수의 경우 제곱근을 더해주면 안된다. 왜냐하면 소수는 오직 1과 자기자신만이 약수이기 때문에 무조건 1 + n이 정답이기 때문이다. 이 점을 제외하면 위와 같은식으로 풀 수 있다. 1을 제외하면 모두 나누어 떨어지지 않기때문에 전부 무시된다.
 
둘째로 합성수이지만 제곱근이 딱 떨어지지 않는 경우이다. 예시로 든 36은 제곱근이 정수 6으로 딱 떨어진다.
 
하지만 12를 예시로 들어보자 
 
12의 제곱근 = 3.46...
이처럼 제곱근이 딱떨어지지 않을경우는 따로 제곱근을 더해주지 않는다 왜냐하면 이들의 특징은 제곱근(소수점 제외)의 대칭수가 있기 때문이다.
1,2,3,4,6,12
 
1 <-> 12
2 <-> 6
3 <-> 4
보다시피 3의 짝인 4가 있다.
 
36의 제곱근 6처럼 딱 떨어지는 경우는 대칭되는 수가 없는 외톨이라고 생각하면 된다. 그래서 제곱근 하나를 더해준다.
12의 제곱근 3.46....과 같은 소숫점이 존재하는 제곱근은 짝이 있으므로 따로 제곱근을 더해주지 않는다.
 
둘의 공통점은 제곱근이 실수인것과 제곱근을 따로 더해주면 안된다는것이다.
 
 
 

---

코드 작성)

나의 풀이

 
1. for(int i=1; i<Math.sqrt(n);i++) //1부터 n의 제곱근까지 반복문을 실행한다. 1부터 시작하는 이유는 1도 더해야 하기 위함이다.
2. if((n%i) == 0) // 1부터 제곱근까지의 숫자 중 n과 나누어 떨어지는 수인가를 검사한다. 맞다면 총합계, i, n나누기i의 몫을 합산한다. 
3. if(Math,sqrt(n)%1 == 0) // 제곱근이 정수라면 (1로 나눈 나머지가 0이면) 제곱근을 추가로 더해준다.

---

의문점 해결)
 
4줄의 for문은 i<Math.sqrt(n) 즉 n보다 작아야 for문이 실행될것이다. for의 실행문은 서로의 대칭수를 합하는 기능을 한다. 하지만 합성수이면서 제곱근이 실수인 경우 대칭되는 수와 합해야하는데 이건 i가 제곱근의 숫자와 같지 않은가? 라는 질문을 할 수 있다.
 
예를 들어 12의 제곱근은 3.46... 이 나오고 3과 4를 합쳐야한다. 그런데 i<Math.sqrt(n)이니 i가 3이되면 합산하지 않고 종료되는것이 아닌가라는 것이다. 
 
Math.sqrt() 함수는 실수형태로 반환한다. 그리고 우리가 더해야하는 숫자는 정수이다. 그러므로 i=3이고 비교대상은 3.46...이니 3보다 크다. 그래서 for문은 정상적으로 실행하고 3과 4를 더하는 작업을 할것이다.