BOJ 14579 덧셈과 곱셈

By kuper0201

Published in 알고리즘

2023-05-25

1 min read

문제

입력

풀이

문제

BOJ 14579 덧셈과 곱셈 바로 가기

남규는 최근에 덧셈과 곱셈을 배웠다.

하지만 도현이는 남규가 제대로 배웠는지에 대해 의심을 가지고 있다.

그래서 도현이는 남규에게 문제를 내기로 했는데, 문제는 아래와 같다.

a, b (1 ≤ a < b ≤ 1000)가 주어졌을 때

$(1+2+…+a) \times (1+2+…+(a+1)) \times … \times (1+2+…+(b-1)) \times (1+2+…+b)$

의 값을 계산하라.

남규는 사실 이 값을 계산하지 못한다.

그래서 남규는 a, b가 주어졌을 때, 위의 값의 결과가 얼마인지 구하는 프로그램이 필요하다.

남규를 위해 위 식을 계산해내는 프로그램을 하나 만들어 주자.

입력

첫째 줄에 a, b (1 ≤ a < b ≤ 1000)가 주어진다.

풀이

해당 문제는 단순히 주어진 식을 계산하라는 구현 문제이다.

식을 곱 연산을 기준으로 나누어 보면 (1+2+...+a), (1+2+...+(a+1)), ... 의 항들은 모두 등차 수열이라는 것을 알 수 있다.

따라서 해당 문제는 등차수열들의 곱을 계산하라는 문제이다.

하지만 a = 100, b = 1000이 주어졌다고 가정해 보았을 때 계산해야 하는 식은 다음과 같다.

$(1+2+...+100) \times (1+2+...+101) \times ... \times (1+2+...+999) \times (1+2+...++1000)$

해당 식을 계산해 보면 64비트 정수형의 표현 범위를 넘어서는 값을 가진다.

따라서 중간에 오버플로우가 발생하여 정상적인 계산이 불가능할 것이다.

이를 해결하기 위해 나머지 연산의 분배 법칙을 알아야 한다.

예를 들어 $(10 \times 11) \% 7$ 을 계산하고자 한다면, 아래와 같은 결과가 도출된다.

110 \% 7 = 5 \newline((10 \% 7) \times (11 \% 7)) \% 7 = 12 \% 7 = 5

분배법칙을 이용하지 않았을 때와 분배법칙을 이용하여 계산 했을 때의 결과가 같은 것을 알 수 있다.

이를 변수를 이용해 일반화 하면 다음과 같다.

(A \times B) \% C = ((A \% C) \times (B \% C)) \% C

이러한 성질을 이용하면 각 항의 계산 결과가 C를 넘지 않을 것이므로 C 미만의 값을 유지하며 최종 결과를 계산 할 수 있다.

코드 보기(Java)

import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // a, b 입력
        String[] s = br.readLine().split(" ");
        int a = Integer.parseInt(s[0]);
        int b = Integer.parseInt(s[1]);

        // 식 계산
        long res = 1;
        for(int i = a; i <= b; i++) {
            // 합 계산
            long sum = 0;
            for (int j = 1; j <= i; j++) sum += j;

            // 곱 계산(값 커질수 있으므로 나머지 연산)
            res *= sum;
            res %= 14579;
        }

        System.out.println(res % 14579);
    }
}

코드 보기(C++)

#include <iostream>

#define fastio ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr)
#define endl '\n'

using namespace std;

int main() {
    fastio;
    
    // a, b 입력
    int a, b;
    cin >> a >> b;

    // 식 계산
    long res = 1;
    for(int i = a; i <= b; i++) {
        // 합 계산
        long sum = 0;
        for (int j = 1; j <= i; j++) sum += j;

        // 곱 계산(값 커질수 있으므로 나머지 연산)
        res *= sum;
        res %= 14579;
    }
    
    cout << res % 14579 << endl;
    
    return 0;
}

코드 보기(Kotlin)

fun main(args: Array<String>) = with(System.`in`.bufferedReader()) {
    // a, b 입력
    var s = readLine().split(" ")
    var a = s[0].toInt()
    var b = s[1].toInt()

    // 식 계산
    var res = 1
    for(i in a .. b) {
        // 합 계산
        var sum = 0;
        for(j in 1 .. i) { sum += j }

        // 곱 계산(값 커질수 있으므로 나머지 연산)
        res *= sum
        res %= 14579
    }
    
    println(res % 14579)
}

코드 보기(Python)

from sys import stdin

def main():
    # a, b 입력
    s = stdin.readline().split(' ')
    a = int(s[0])
    b = int(s[1])

    # 식 계산
    res = 1
    for i in range(a, b + 1):
        # 합 계산
        sum = 0
        for j in range(1, i + 1):
            sum += j

        # 곱 계산(값 커질수 있으므로 나머지 연산)
        res *= sum
        res %= 14579

    print(res % 14579)

if __name__ == "__main__":
    main()

코드 보기(Swift)

import Foundation

func main() {
    // a, b 입력
    var s = readLine()!.split(separator: " ")
    var a = Int(s[0])!
    var b = Int(s[1])!

    // 식 계산
    var res = 1
    for i in a ... b {
        // 합 계산
        var sum = 0;
        for j in 1 ... i {
            sum += j
        }

        // 곱 계산(값 커질수 있으므로 나머지 연산)
        res *= sum;
        res %= 14579;
    }
    
    print(res % 14579)
}

main()