[java] 백준 2355번 시그마

전에는 쉬운 알고리즘 문제 풀면서 시간제한이 1~2 초거나 범위가 꽤 크지 않았다.

 

하지만 이제는 점차 시간제한도 있고 범위가 상당하다... 

 

처음에 접근한 방식이다.

1. 범위가 int 형이어서 int형을 써보았지만 StackOverflow...
2. Long을 써봤는데도 StackOverflow...
3. 검색해보니 재귀를 많이 돌리면 stackoverflow가 난다고 했다. 아래의 소스는 재귀로 돌렸을 때 결과는 잘 나오지만
   백준에 냈을 때 stackoverflow가 나온 결과
   

   import java.util.Scanner;
   
   public class Main {
       public static void main(String[] args) {
           Scanner sc = new Scanner(System.in);
           long A = sc.nextLong();
           long B = sc.nextLong();
   
           System.out.println(recur(A, B));
   
       }
   
       public static Long recur(long A, long B){
           if(A>B){
               return recur(A-1, B)+A;
           }else if(A<B){
               return recur(A, B-1)+B;
           }else{
               return A;
           }
       }
   }​

4. 그래서 내 코드가 문제인 것 같아서 검색을 해봤다. '가우스 덧셈'
   공식은 1부터 n까지의 합 : n x (n+1) / 2 이다. 근데 내가 풀어야할 문제는 a부터 b까지의 합이라서 
   n에다 a랑 b를 어떻게 조합해야할지 몰라서 일단 사칙연산의 기본적인 곱,나누기, 합, 차를 맞춰보았다.
   그 이후는 노가다... 시간이 흘러서 (a+b) x (b-a+1) / 2 라는 공식이 나왔다. 

 

A와 B 중 어느 게 큰 수로 나올지 모르기 때문에 if문으로 A가 클 때와 B가 클 때를 나눠서 조건을 걸어줬다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long A = sc.nextLong();
        long B = sc.nextLong();

        System.out.println(sigma(A, B));

    }

    public static Long sigma(long A, long B){
        if(A>=B)
            return (A+B)*(A-B+1) / 2;
        else
            return (B+A)*(B-A+1) / 2;

    }
}

그렇게 시간 초과도 나오지 않았고 stackoverflow도 나오지 않았다.

 

여담)

.

.

.

 

solved.ac라는 곳에서 백준 문제를 티어별로 나누어놨다. 

자신이 푼 문제들을 티어별로 볼 수 있고 현재 나 같은 경우는 실버 4이다.

꽤 올라가야만 하는.... ㅠㅠ

solved.ac - 검색