백준 1419번: 등차수열의 합

등차수열의 i번째 항이 x + (i-1)*d 로 표현되고(x는 첫번째 항, d는 공차) x, i, d 가 자연수일 때, 주어진 구간 안에서 첫번째 항부터 k번째 항 까지의 합이 될 수 있는 값의 갯수를 구하는 문제이다. k는 2보다 크거나 같고 5보다 작거나 같은 자연수이다.

 

k가 2, 3 ,4, 5 마다 가지는 규칙을 이용하여 해결한다. k가 2인 경우, 모든 항을 더하면 2x + d가 되어 구간에서 3보다 크거나 같은 자연수의 갯수가 된다. 3의 경우, 모든 항을 더하면 3x + 3d로 구간에서 6보다 크거나 같은 모든 3의 배수의 갯수가 된다. 4의 경우, 4x + 6d로 구간 내에서 12를 제외한 10보다 크거나 같은 2의 배수의 갯수가 된다. 5의 경우, 5x + 10d로 구간에서 15보다 크거나 같은 모든 5의 배수의 갯수가 된다.

if (k == 2) {
    long start = Math.max(l, 3);
    if (start <= r) {
        count = r - start + 1;
    }
} else if (k == 3) {
    long start = Math.max(l, 6);
    count = countMultiples(start, r, 3);
} else if (k == 4) {
    long start = Math.max(l, 10);
    count = countMultiples(start, r, 2);
    if (start <= 12 && 12 <= r) {
        count--;
    }
} else if (k == 5) {
    long start = Math.max(l, 15);
    count = countMultiples(start, r, 5);
}

 

 

특정 구간의 특정 숫자의 배수의 갯수를 구하기 위해서 (오른쪽 / 특정 숫자 - (왼쪽 - 1)/ 특정 숫자) 를 계산한다.

private static long countMultiples(long L, long R, long m) {
    if (L > R) {
        return 0;
    }
    return (R / m) - ((L - 1) / m);
}

 

 

결과 코드는 다음과 같다.

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

public class 등차수열의합1419 {
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long l = Long.parseLong(br.readLine()), r = Long.parseLong(br.readLine());
        long k = Long.parseLong(br.readLine());
        br.close();
        long count = 0;
        
        if (k == 2) {
            long start = Math.max(l, 3);
            if (start <= r) {
                count = r - start + 1;
            }
        } else if (k == 3) {
            long start = Math.max(l, 6);
            count = countMultiples(start, r, 3);
        } else if (k == 4) {
            long start = Math.max(l, 10);
            count = countMultiples(start, r, 2);
            if (start <= 12 && 12 <= r) {
                count--;
            }
        } else if (k == 5) {
            long start = Math.max(l, 15);
            count = countMultiples(start, r, 5);
        }
        System.out.print(count);
    }
    
    private static long countMultiples(long L, long R, long m) {
        if (L > R) {
            return 0;
        }
        return (R / m) - ((L - 1) / m);
    }
}