[BJ] 7523. Gauß

 

BJ 7523. Gauß

https://www.acmicpc.net/problem/7523

7523번: Gauß

 

 

생각

왜 시간 복잡도에 대한 고려가 필요한지 살펴보는 문제이다. 

간단한 구간 더하기 이므로 for 문을 이용할 수 있지만 N 제한이 -10^9 ≤ n ≤ m ≤ 10^9 으로 O(N)이 10억을 넘는다.

 

따라서 Gauß의 더하기 연산을 통해서 처리해줘야 한다.

추가로 더하기의 결과가 int의 범위를 넘기 때문에 long으로 처리해 주어야 한다.

 

 

코드 구현

 

Java

package bj.bronze.l3;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.StringTokenizer;

/**
 * @author 은서파
 * @since 2023. 1. 24.
 * @see
 * @git
 * @youtube
 * @performance 12128   92
 * @category #수학
 * @note N제한이 20억이므로 linear 연산으로는 1초에 들어올 수 없다.
 */

public class BJ_B3_07523_Gaus {

    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder output = new StringBuilder();
    static StringTokenizer tokens;
    static int T;
    static int N, M;
    static long A;
    public static void main(String[] args) throws IOException {
        input = new BufferedReader(new StringReader(instr));
        T = Integer.parseInt(input.readLine());
        for(int t=1; t<=T; t++) {
            tokens = new StringTokenizer(input.readLine());
            N = Integer.parseInt(tokens.nextToken());
            M = Integer.parseInt(tokens.nextToken());

            A = 0;
            //linearSum();
            gausSum();
            //output.append(String.format("Scenario #%d:\n%d\n\n", t+1, A));
            output.append("Scenario #").append(t).append(":\n").append(A).append("\n\n");
            
        }
        System.out.println(output);
    }
    static void gausSum() {
        A = 1L*(M-N+1)*(M+N)/2;
    }
    
    static void linearSum() {
        if(N>M) {
            int temp = N;
            N = M;
            M = temp;
        }
        for(int i=N; i<=M; i++) {
            A+=i;
        }
        
    }

    // REMOVE_START
    public static String instr = "3\n"
                                 + "1 100\n"
                                 + "-11 10\n"
                                 + "-89173 938749341";
    // REMOVE_END

}