[백준 알고리즘] 17173번 : 배수들의 합

문제

신원이는 백준에서 배수에 관한 문제를 풀다가 감명을 받아 새로운 문제를 만들어보았다. 자연수 N과 M개의 자연수 Ki가 주어진다. Ki중 적어도 하나의 배수이면서 1 이상 N 이하인 수의 합을 구하여라.

입력

첫 번째 줄에 N과 M가 주어진다. (2 ≤ N ≤ 1000, 1 ≤ M < N)
그다음 줄에 M개의 정수 Ki가 주어진다. (2 ≤ Ki ≤ 1000)
동일한 Ki는 주어지지 않으며, 오름차순으로 정렬되어있다.

출력

배수들의 합을 출력한다.

예제 입력 1

10 2 2 3

예제 출력 1

42

예제 입력 2

1000 3 3 5 7

예제 출력 2

272066

출처

University > 충남대학교 > 제3회 생각하는 프로그래밍 대회 A번

 

내가 작성한 코드 (C++ 성공)

#include <iostream>

using namespace std;

int main(){
	int n, m;
	int sum = 0;
	cin >> n >> m;
	
	int k[m+1] = {0};
	int b[n+1] = {0};
	
	for(int i=0; i<m; i++){
		cin >> k[i];
	}
	
	for(int i=0; i<m; i++){
		for(int j=1; j<=n; j++){
			if(j%k[i] == 0) b[j] = j;
		}
	}
	
	for(int i=1; i<=n; i++){
		sum += b[i];
	}
	
	cout << sum;
	
	return 0;
}

 

정리

이 문제를 간단하게 말하면 여러 수의 배수들의 합을 구하면서 중복되지 않아야한다.
배수를 구하는 건 해당 수를 나눈 나머지가 0이면 배수를 구할 수 있기 때문에 금방 구할 수 있었다.
조금 고민했던 부분은 중복된 배수를 어떻게 걸러주는냐인데
나는 배열 값을 덮어써주는 방법을 통해 문제를 풀었다.
만약 각각의 숫자를 따로 배수를 구해서 더해주면 중복되기 때문에
예를 들어,
2와 3의 배수의 합을 구한다고 생각해보자.
2의 배수에는 6이 있고, 3의 배수에도 6이 있다.
각각의 배수를 구해서 더해준다면 6이 두번 더해진다.
하지만 배열을 이용하면 2의 배수 6를 넣어주고 다시 3의 배수 6을 넣어주면
같은 자리에 넣어주기 때문에 중복되어도 배열의 값은 하나가 된다.

1) 범위와 숫자의 갯수를 입력받는다.
2) 정해진 범위 내에 있는 숫자의 배수를 구한다.
3) 범위 만큼의 크기를 가진 배열을 만들어서 배수인 경우 배열에 넣어준다.
4) 배수를 넣어준 배열들의 합을 구한다.