[백준/BOJ] 2355번 : 시그마 (JAVA / 자바)

안녕하세요~ 코딩하는 코알못 코메인입니다.

 

 

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

2355번: 시그마

---

- 문제 -

 

난이도 브론즈 3 문제이다.

 

자바에서 입력방식은 scanner와 bufferedreader가 있다.

자바를 초반에 접하면 처음에 배우는 입력은 scanner이다. scanner가 bufferedreader보다 편하지만 속도가 느리다.

bufferedreader는 무조건 문자열로 받아오기때문에 정수형이나 실수형 변수에 저장하기 위해서는 입력과 형변환을 해줘야한다.

더 자세한 내용은 아래 글 참고 하면 좋다.

https://comain.tistory.com/3

(JAVA / 자바) Scanner 와 Bufferedreader

 

풀이 방법

지금까지 백준 풀면서 제일 짜증났던 문제 같네요... 정말 많이 틀리고 몇시간을 고민했는데....

풀이 자체는 제대로 풀었지만 문제에 연연한 나머지 제대로 풀어내질 못했다... 답의 범위가 int형 범위로 제한 해둬서 long을 쓰면 안되는 줄 알고 어떻게 풀어내야할지 연산 결과 int 범위를 벗어 날 수 밖에 없는데 어떻게 처리해야할지 이래저래 고민하다가 결국 풀이를 봤는데 그냥 다들 long형을 쓰더라... 정말 허무할 수 밖에 없었네... 내 시간과 고민하느라 쓰인 노력, 기분은 다 어찌... 시도를 안해본 나도 멍청했지만...그저 한탄이다... 한탄이 길어졌네...

 

결국 long형으로 풀란거다....

 

두가지의 방법으로 풀었습니다.

입력값중 작은 수를 A/ 높은수를 B라 하겠음

첫번째 : 기본적인 합 공식(1~ B까지의 합)에서  (1~A까지의 합)을 빼는 방법.

두번째 : (A + B) == ((A+1) + (B-1))가 성립 되는데 그렇게 가운데로 하나씩 줄여서 더한 값들은 다 같다.  그럼 맨 끝의 값이 계속 반복되는데 그 횟수는 A부터 B까지의 수의 갯수의 반이다. 식으로 보여주겟다.

 

우선 입력 값 중 큰수와 작은 수는 직접 비교해야하는 나는 Math.min과 max를 사용해서 선 비교후 연산을 했다.

 

-식-

첫번째 : 1~B까지의 합 : ((B + 1) * B) / 2 | 1~ A까지의 합 : ((A - 1) * A) / 2

두 합의 차를 구하면 A와 B의 사이 수들의 합이 나온다. ((B + 1) * B) / 2 - ((A - 1) * A) / 2

 

두번째 : 끝의 두 수의 합 : (A + B) | 같은 수의 반복 수는 ((B - A) + 1) / 2

이 두 값의 곱을 구하면 사이 수들의 합이 나온다. (A + B) * ((B - A + 1) / 2)

그런데 두번째 방법은 반복수가 홀 수일 경우 가운데 한 수가 남아 버린다. 홀 수 일 경우 그 수를 더해준다. (한 가운데 수의 값은 (A + B) / 2 이다.

코드를 보자.

---

-풀이-

첫번째 방법

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

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		long N = Long.parseLong(st.nextToken());
		long M = Long.parseLong(st.nextToken());
        //큰 수와 작은 수를 A와 B에 저장
		long A = Math.min(N, M);
		long B = Math.max(N, M);
		long sum = (((B + 1) * B) / 2) - (((A - 1) * A) / 2);
		
		System.out.println(sum);
	}

}

두번째 방법

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

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		long N = Long.parseLong(st.nextToken());
		long M = Long.parseLong(st.nextToken());
		long A = Math.min(N, M);
		long B = Math.max(N, M);
		long sum = (A + B) * ((B - A + 1) / 2);
		
		if((B - A + 1) % 2 != 0) {
			sum += (A + B) / 2;
		}
		System.out.println(sum);
	}

}

 

풀이 방법에서 상세히 설명해 놓았기에 코드에 설명은 생략하겠다.

---

-결과-

첫번째 방법

두번째 방법

---

두번째 방법이 시간복잡도 적으로 더 빠르긴 하다.

 

아직 코딩 공부가 부족한 필자라 설명과 풀이 방법이 많이 미흡할 수 있다. 코딩 고수들은 보시고 문제점이 있다면 댓글로 말해주시면 감사한 마음으로 참고 수정 하겠다.