백준 - 배수들의 합(Kotlin, Java)

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.

https://github.com/ROUTINE-STUDY/Algorithm

 

저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능

문의는 댓글 바람.

 

문제 출처 :https://www.acmicpc.net/problem/17173

 

[문제 설명]

주어진 숫자들의 배수 중에서 N보다 작은 값들의 총합.

 

[접근 방법]

N이 최대 1000이므로 방문여부를 기록하는 Boolean 배열을 만들어줬다.

Boolean형의 크기는 2Byte이므로 2000Byte -> 2mb가 좀 안 된다.

따라서, 공간복잡도는 O(N)

 

시간복잡도는

1개의 숫자를 체크하는데 O(N/Ki) -> 만약, N이 10이고 Ki이 2면 5번(M의 배수 2,4,6,8,10) 체크함

전체 숫자의 개수는 M개이므로 O(M*(N/Ki))이 될 듯하다.

 

[처음 작성한 코드]

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val (N, M) = readLine().split(" ").map {it.toInt()}
    val isVisited = BooleanArray(1001)
    var sum = 0

    // it은 현재 Ki의 값
    readLine().split(" ").map { it.toInt() }.forEach {
    	// 현재 값
        var currentNum = it
        // 곱할 숫자
        var multipliedNum = 2
        
        // 현재 값이 N보다 작은동안만 반복
        while (currentNum <= N) {
            // 전에 더한 숫자가 아니면 더하고, 방문처리
            if (!isVisited[currentNum]) {
                isVisited[currentNum] = true
                sum += currentNum
            }
            // Ki의 배수
            currentNum = it*multipliedNum++
        }
    }

    println(sum)
}

 

코드를 작성하고 다른 사람의 코드를 봤는데 단순하게 곱하는 게 아닌, 배수 자기 자신을 더하는 방법을 사용했다.

차라리 이게 훨씬 깔끔한 느낌이다.

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val (N, M) = readLine().split(" ").map {it.toInt()}
    val isVisited = BooleanArray(1001)
    
    var sum = 0
    readLine().split(" ").map { it.toInt() }.forEach {
        var currentNum = it
        while (currentNum <= N) {
            if (!isVisited[currentNum]) {
                isVisited[currentNum] = true
                sum += currentNum
            }
            // 배수를 곱하는 게 아닌 더함
            currentNum += it
        }
    }

    println(sum)
}

[Java 코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

class Main {
    public static void main(String[] args) throws IOException {
        int answer = 0;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] inputs = Arrays.stream(br.readLine().split(" ")).mapToInt(it -> Integer.parseInt(it)).toArray();
        int N = inputs[0];
        int M = inputs[1];
        boolean[] isVisited = new boolean[N+1];

        inputs = Arrays.stream(br.readLine().split(" ")).mapToInt(it -> Integer.parseInt(it)).toArray();
        for (int i = 0; i < inputs.length; i++) {
            for (int currentNumber = inputs[i]; currentNumber <= N; currentNumber+=inputs[i]) {
                if (!isVisited[currentNumber]) {
                    answer += currentNumber;
                    isVisited[currentNumber] = true;
                }
            }
        }

        System.out.println(answer);
    }
}