백준 1789번 : 수들의 합 (JAVA 자바)

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

1789번: 수들의 합

 

문제

서로 다른 N개의 자연수의 합이 S라고 한다. S를 알 때, 자연수 N의 최댓값은 얼마일까?

 

입력

첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다.

 

출력

첫째 줄에 자연수 N의 최댓값을 출력한다.

 

풀이

 

200이라는 자연수 S가 주어졌을때,

 

서로 다른 자연수 N를 더해 S를 만들 때 N이 최대값이 되려면, 가장 작은 수 부터 차근차근 더해야 할것이다.

 

1+2+3+4+5... 쭉쭉 더해가다보면 200을 넘는 순간이 있을 것이다.

 

이때 반복문을 멈추고 마지막으로 더한 숫자를 확인해보면 20, 합은 210이다.

 

1~20까지의 숫자를 더해 210이 나왔고 여기서 10을 빼면 200이 만들어진다.

 

19개의 자연수로 200을 만드는 것이 된다.

 

S 이상의 자연수가 나올때까지 1부터 더하고 S이 넘는 순간의 자연수 개수 -1 이 답이다.

 

 

에러 해결

 

구현 자체는 쉬운 문제였지만 런타임 에러 (InputMismatch)가 떴다.

 

주어진 S 의 범위는 1 ≤ S ≤ 4,294,967,295 인데

int 의 범위는 -2,147,483,648 ~ 2,147,483,647 이기 때문에 생긴 오류다.

 

이를 해결하기 위해 구글링하며 long 과 BigInteger로 해결하는 법 두가지를 발견했다.

 

타입	범위	메모리크기	데이터 타입	자로형
int	-2,147,483,648 ~ 2,147,483,647	4 Byte	기본형	정수형
long	-9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807	8 Byte	기본형	정수형
BigInteger	무한 (Infinity)	Minimum 70 Byte	참조형	문자열 형태

 

참조형의 경우 기본형을 제외한 나머지 타입, 객체의 주소를 말한다.
그리고 new 키워드를 통하여 객체를 생성, 초기화 해야 한다.

 

int와 long 의 범위를 벗어날때 BigInteger을 사용한다.

 

이 문제는 long으로도 해결할 수 있지만, BigInteger을 알게 되어서 BigInteger로도 풀어보았다.

 

long을 사용한 코드 

import java.util.*;

public class Main {
	public static void main(String[] args) {
		
		Scanner in = new Scanner(System.in);
		
		long s = in.nextLong();
		long plus = 1;
		long sum = 0;
		while(true) {
			sum += plus;
			if(sum>s) break;
			plus ++;
		}
		System.out.println(plus-1);
		
	}
}

 

BigInteger를 사용한 코드 

import java.util.*;
import java.math.*; // BigInteger은 math 클래스에 있기 때문에 import 해주어야함

public class Main {
public static void main(String[] args) {
	
	Scanner in = new Scanner(System.in);
	
	BigInteger s = in.nextBigInteger();
    
    // 정수형과는 선언이 다른 것을 알 수 있다.
	BigInteger plus = new BigInteger("1");
	BigInteger sum = new BigInteger("0");
	
	while(true) {
		sum = sum.add(plus); // BigInteger 더하기
		if(sum.compareTo(s) == 1) break; // BigInteger의 크기 비교
		plus = plus.add(BigInteger.valueOf(1));
	}
	
	System.out.println(plus.subtract(BigInteger.ONE)); // BigInteger 빼기
}
}

 

 

 BigInteger 의 연산과 크기 비교 함수

더하기 : add()
빼기   : subtract()
곱하기 : multiply()
나누기 : divide()

- 더하기 1
  num = num.add(BigInteger.ONE);

- 더하기 2
  num = num.add(BigInteger.valueOf(2));

 - 빼기 3
  num = num.subtract(BigInteger.valueOf(3));

- 곱하기 2
  num = num.multiply(BigInteger.valueOf(2));

- 나누기 2
  num = num.divide(BigInteger.valueOf(2));

-곱하기 0
  num = num.multiply(BigInteger.ZERO);

  if (num1.compareTo(num2) == 0) {
    두 숫자가 같을때
} else if (num1.compareTo(num2) == -1) {
    num1이 num2 보다 작을때
} else if (num1.compareTo(num2) == 1) {
    num이 num2 보다 클때
}