[문제풀이][Java] 백준 1789번 수들의 합 풀이(서로 다른 N개의 자연수의 합이 S라고 한다. S를 알 때, 자연수 N의 최댓값은 얼마일까?)

[문제풀이][Java]  백준 1789번 수들의 합 풀이(서로 다른 N개의 자연수의 합이 S라고 한다. S를 알 때, 자연수 N의 최댓값은 얼마일까?)

문제 링크 : https://www.acmicpc.net/problem/1789

* 학습 목적의 게시물이나 혹시 이 게시물이 문제가 된다면 언제든 연락 부탁드립니다.

* 더 나은 풀이를 위한 훈수, 조언 등 모두 환영합니다!

---

문제

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

입력

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

출력

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

---

해결 방법

1. 하나씩 더해가며 생각하는 방법

• 서로 다른 N개의 자연수의 합인 S가 주어지고 N을 최대로 하기 위해서는 제일 작은 자연수부터 더해 쌓아나가야 한다. 
• N이 최대가 되기 위해서는 아래 식을 만족하는 경우가 가장 크다.
• 1 + 2 + .... + n + a = S (a <= n)
• 위 식에 따르면 a는 1부터 n까지의 수에 중복이 됨으로, n에 붙여 (n + a)라는 자연수로 인지한다.
• 따라서 1부터 하나씩 카운트해가며 더한 값이 S보다 크거나 같을 때까지 확인하고,
• 크다면 카운트한 값에서 1을 빼서 N을 구할 수 있다.

2. 수식 적용

• 1 + 2 + .... + n = ((n + 1) * n) / 2
• ((n + 1) * n) / 2 + a = S (a <= n)
• (n + 1) * n <= S * 2
• 이를 만족하는 m을 추정 : m^2 = s * s
• m을 하나씩 더해가며 n을 찾을 수 있다.

---

전체 코드

1. 하나씩 더해가며 생각하는 방법

import java.util.Scanner;

public class B1789 {
	
	public static void main(String[] args) {
		
		// 입력 받기
		Scanner scan = new Scanner(System.in);		
		long sum = scan.nextLong();
		scan.close();
		
		// 최대한 많은 서로 다른 자연수의 합으로 S를 구성하기 위해서는 작은 수부터 쌓아나가야 한다.
		long num = 0;
		int count = 0;
		while(sum >= num) { // 1부터 더해가며 그 합이 주어진 수를 넘지 않는지 확인
			num += (++count);
		}
		if(sum < num) { // 넘었다면 이전에 자연수 중에 하나를 빼면 되기에 -1
			count--;
		}
		System.out.println(count);
		
	}

}

---

참고사항

입력 숫자의 범위가 커 long타입을 쓰지 않으면 시간 초과가 걸린다.