문제

배수들의 합

문제 설명

• 정수 N과 K가 주어진다.
• 이후 K개의 자연수가 주어진다. (배수 기준 숫자들)
• 1부터 N까지의 수 중에서 주어진 수들의 배수인 수들의 합을 구하는 문제.

문제 풀이 방법

• 각 K[i]의 배수를 더하기
• 만약 같은 배수값이 중복 된다면 한 번만 더할 것

예) 더해야 할 배수의 값이 2 3 일 경우

2 4 6 8 10
3 6 9

6이 두 번 나오기 때문에 한 번만 더 할 것

코드

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[] K = new int[M];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            K[i] = Integer.parseInt(st.nextToken());
        }

        boolean[]  visited = new boolean[N+1];
        int sum = 0;
        for(int num: K){
            for(int i = num; i <= N; i += num){
                if(!visited[i]){
                    visited[i] = true;
                    sum += i;
                }
            }
        }
        System.out.println(sum);
    }
}

코드 설명

1. visited[i]: i가 이미 더해졌는지 확인

2. for (int i = num; i <= N; i += num): num의 배수만 탐색하므로 효율적

3. 중복 방지 덕분에 2와 3의 공배수인 6, 등은 한 번만 더해짐