[ 프로그래머스 [ 월간코드챌린지 ] 약수의 개수와 덧셈 ] (C++)

프로그래머스의 약수의 갯수와 덧셈(월간코드챌린지) 문제이다.

 

[ 문제풀이 ]

입력으로 주어지는 숫자의 범위에서, 약수의 갯수가 짝수인 숫자는 더하고 홀수인 숫자는 뺐을 때 그 결과값을 구해야 하는 문제이다.

 

#1. 풀이1

정말 간단하게 문제에 접근을 해보자. 우리는 Left ~ Right범위 내에 있는 각각의 숫자들이 약수의 갯수가 몇 개인지 그리고 이 갯수를 통해서 그 갯수가 홀수개인지 짝수개인지만 판단을 해주면 된다.

그럼 직접 모든 약수를 다 구해보고 그 갯수를 Count해주는 방법으로 이를 해결할 수가 있다.

약수의 갯수를 구하는 과정은 다음과 같이 구할 수 있다.

int Calculate(int x)
{
	int Cnt = 0;
	for (int i = 1; i <= x; i++)
	{
		if (x % i == 0)Cnt++;
	}
	return Cnt;
}

주어진 'x'라는 숫자의 약수를 구하는 방법이다. 1 ~ x까지 반복하면서 나누어 떨어지는 숫자가 x의 약수라는 의미이기 때문에 위와 같이 구할 수가 있다.

주어진 범위 Left ~ Right에 속해있는 모든 숫자들을 위와 같이 약수를 구해서 그 갯수를 Count하고 홀수인지 짝수인지 판단하더라도 시간초과도 발생하지 않고 충분히 pass를 받을 수 있다.

 

#2. 풀이2

지금부터는 보다 조금은 다른 풀이 방법을 이야기해보려고 한다.

본인은 이 문제를 루트를 이용해서 접근해 보았다.

우리는 사실 어떤 숫자의 약수의 갯수가 몇 개인지는  몰라도 된다. 그 갯수가 홀수개인지 짝수개인지만 알면 된다.

그럼, 약수의 갯수가 짝수개라는 것은 무엇을 의미할까 ??

바로 "제곱수에 의해 만들어지는 숫자가 아니다" 라는 것을 의미한다.

몇 가지 예를 들어보자.

숫자 '3'

'3'의 약수는 [ 1 , 3 ] 이 있고 약수의 갯수는 짝수 개이다.

숫자 '5'

'5'의 약수는 [ 1 , 5 ] 가 있고 약수의 갯수는 짝수 개이다.

숫자 '10'

'10'의 약수는 [ 1 , 2 , 5 , 10 ] 이 있고 약수의 갯수는 짝수 개이다.

위의 숫자들인 '3', '5', '10'은 어떤 수의 제곱꼴로 나타낼 수 없다는 특징이 있다.

 

반대로 약수의 갯수가 홀수인 경우를 한번 살펴보자.

숫자 '4' : 2의 제곱으로 표현이 가능하다.

'4'의 약수는 [ 1 , 2 , 4 ] 가 있고 약수의 갯수는 홀수 개이다.

숫자 '9' : 3의 제곱으로 표현이 가능하다.

'9'의 약수는 [ 1 , 3 , 9 ] 가 있고 약수의 갯수는 홀수 개이다.

숫자 '16' : 4의 제곱으로 표현이 가능하다.

'16'의 약수는 [ 1 , 2 , 4 , 8 , 16] 이 있고 약수의 갯수는 홀수 개이다.

위의 숫자들인 '4', '9', '16'은 어떤 수의 제곱꼴로 나타낼 수 있다는 특징이 있다.

 

그렇다면 왜 어떤 수의 제곱꼴로 나타낼 수 있는 숫자들은 약수의 갯수가 반드시 홀수 개일까 ??

그 이유는 "하나의 숫자로 표현이 가능" 하기 때문이다.

숫자 '10'을 생각해보자. 약수는 [ 1 , 2 , 5 , 10 ] 이 있는데, 이 약수들은 2개씩 짝을 지어야만 '10'을 표현할 수가 있다.

1과 10을 곱해서 10을 만들 수 있고, 2와 5를 곱해서 10을 만들 수 있다.

즉 ! 반드시 짝수개가 있어야만 해당 숫자를 표현할 수 있기 때문에 어떤 수의 제곱꼴로 나타낼 수 없는 숫자들은 반드시 약수의 갯수가 짝수개가 된다.

숫자 '16'을 생각해보자. 약수는 [ 1 , 2 , 4 , 8 , 16 ] 이 있는데, 이 약수들 중에서 특정 숫자는 하나의 숫자만으로도 '16'을 표현할 수가 있다.

1과 16을 곱해서 16을 만들 수 있고 , 2와 8을 곱해서 16을 만들 수 있지만, '4'같은 경우에는 4혼자만으로도 4^2으로 16을 만들 수 있다. 즉 ! 이것 때문에 어떤 수의 제곱꼴로 나타낼 수 있는 숫자들은 약수의 갯수가 반드시 홀수개라는 특징이 있다.

 

지금부터 그럼 특정 숫자를 어떤 수의 제곱꼴로 나타낼 수 있는지 어떻게 알 수 있을까 ??

본인은 이 과정에서 루트를 사용해 주었다. 지금부터 편의상 루트를 씌운 특정 숫자를 R(X) 라고 표현하겠다.

R(5)는 얼마일까 ? 아마 2.xxx 정도 될 것이다.

R(10)은 얼마일까 ? 아마 3.xxx 정도 될 것이다.

R(9)는 얼마일까 ? 정확하게 3.0000 이 될 것이다.

R(16)은 얼마일까 ? 정확하게 4.0000 이 될 것이다.

즉 ! 어떤 수의 제곱꼴로 나타낼 수 있는 숫자냐 아니냐는 루트를 씌웠을 때 뒤의 소수점이 0으로만 이루어져 있냐 아니냐로 구분을 할 수가 있다.

즉 ! 특정 숫자 K가 어떤 수의 제곱꼴로 나타낼 수 있는지 확인을 하고 싶다면...

(double)( R(K) - (int)(R(K)) )

위의 식의 값을 확인하면 될 것이다.

위의 식을 보면, R(K) 에서 R(K)의 int형 부분만 빼낸 것이다.

즉, K = 5라고 가정을 해보면,

R(K) = 2.xxxx

(int)(R(K)) = 2

가 될 것이다. 여기서 R(K) - (int)(R(K)) 를 연산하게 되면 0.xxxx 가 나오게 될 것이다.

즉 ! 위의 값이 0.0이냐 아니냐를 통해서 해당 숫자가 어떤 수의 제곱꼴로 나타낼 수 있는지 아닌지를 확인할 수 있다.

 

[ 소스코드 ]

#include <string>
#include <vector>
#include <cmath>
 
using namespace std;
 
int solution(int left, int right)
{
    int answer = 0;
    for (int i = left; i <= right; i++)
    {
        double Sqrt_Num = sqrt(i);
        if (double(Sqrt_Num - (int)Sqrt_Num) == 0.0) answer -= i;
        else answer += i;
    }
    return answer;
}