[C++] 1부터 N까지 M의 배수합

📄문제

자연수 N이 입력되면 1부터 N까지의 수 중 M의 배수합을 출력하는 프로그램을 작성하시오.

 

ℹ️ 조건

3 <= M < N <= 1000

 

⬇️ 입력

첫 줄에 자연수 N과 M이 차례대로 입력한다.

 

⬆️ 출력

첫 줄에 M의 배수합을 출력한다.

 

📝 풀이

• 첫 번째 풀이는 가장 단순하고, 직관적인 방법으로 해결하였습니다.

#include <iostream>

using namespace std;

int main()
{
    int N, M;
    cin >> N >> M;

    int i = M;
    int sum = 0;

    for (int i = 1; i <= N; ++i)
        if (i % M == 0)
            sum += i;

    cout << sum;
}

• 반복문 for (int i = 1; i <= N; ++i)은 1부터 N까지의 숫자를 반복하면서 다음을 수행합니다:
• if (i % M == 0): 현재 숫자 i가 M으로 나누어 떨어지는지 확인합니다. 즉, i가 M의 배수인지 검사합니다
• 만약 i가 M의 배수라면, sum += i;를 통해 sum 변수에 i 값을 더합니다. 이것은 M의 배수들의 합을 계속해서 누적합니다.

 

• 두 번째 풀이는 M까지의 반복을 피하고, 최솟값과 최댓값을 이용하여 등차수열의 합 방식을 이용하였습니다.

#include <iostream>

using namespace std;

int main()
{
	int N, M;
	cin >> N >> M;

	// 배수의 개수
	int cnt = N / M;

	// 최소값
	int min = 1;
	for (; min <= N; ++min)
		if (min % M == 0)
			break;

	// 최대값 
	int max = N;
	for (; max >= 1; --max)
		if (max % M == 0)
			break;

	// 결과 (개수가 홀수인경우 중간 값 더해주기)
	int sum = (min + max) * (cnt / 2) + (cnt % 2 == 1 ? (min + max) / 2 : 0);

	// 결과 출력
	cout << sum;
}

 

• N을 M으로 나누어서 cnt라는 변수에 M의 배수의 개수를 저장합니다. 
• 최솟값 min을 찾을 때는 1부터 N까지 순차적으로 탐색하고 최댓값 max를 찾을 때는 N부터 1까지 역순으로 탐색합니다.
• 이렇게 하여 min과 max를 찾아냅니다.
• 홀수 개의 배수가 있는 경우 중간값을 더해주는 로직을 사용하여 합을 계산합니다.

 

• 세 번째 풀이는 반복 자체를 제거하고, 조건을 이용하여 최대 및 최솟값을 즉시 찾아내어 계산합니다.

#include <iostream>

using namespace std;

int main()
{
	int N, M;
	cin >> N >> M;

	// 배수의 개수
	int cnt = N / M;

	// 최소값
	int min = M;

	// 최대값 
	int max = N - N % M;

	// 결과 (개수가 홀수인경우 중간 값 더해주기)
	int sum = (min + max) * (cnt / 2) + (cnt % 2 == 1 ? (min + max) / 2 : 0);

	// 결과 출력
	cout << sum;
}

• cnt 변수를 사용하여 N을 M으로 나눈 몫을 저장합니다. 이것은 M의 배수의 개수를 나타냅니다.
• 최솟값 min은 M으로 설정되어 있습니다. 이것은 M의 가장 작은 배수입니다.
• 최댓값 max는 N에서 N을 M으로 나눈 나머지(N % M)를 뺀 값으로 설정됩니다. 이것은 N보다 작거나 같은 M의 가장 큰 배수입니다.
• 반복문 없이 바로 min과 max를 계산하고, 중복 계산을 피합니다.
• cnt / 2를 사용하여 중복 계산을 최소화하고 합을 계산합니다.
• 홀수 개의 배수가 있는 경우 중간 값을 더해줌으로써 더 간결하게 결과를 계산합니다.