[백준] 자바 1789 수들의 합

문제

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

입력

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

출력

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

---

테스트 케이스

 

입력 1

4000000000

출력 1

89442

 

입력 2

200

출력 2

19

 

입력 3

2

출력 3

1

---

접근

1. 수 하나를 입력받습니다.

2. 최대한 숫자를 많이 이용하면서 서로 다른 숫자를 이용한다고 할 때, 몇 개의 수를 써야 하는지 출력해줍니다.

 

1은 1로만 이루어집니다.

2는 서로다른수로 만들기 위해선 2로만 만들 수 있습니다.

3은 1+2로 만들 수 있습니다.

4는 1+3으로 만들 수 있습니다.

5는 1+4로 만들 수 있습니다.

6은 1+2+3으로 만들 수 있습니다.

여기까지 하다보면 규칙이 보입니다.

 

1은 1가지

1+2, 즉 3보다 작은 값은 1가지

1+2+3, 즉 6보다 작은 값은 2가지

1+2+3+4, 즉 10보다 작은 값은 3가지

....

이를 이용하여 코드를 짜니 문제가 해결되었습니다.

 

---

코드

import java.awt.desktop.SystemEventListener;
import java.io.*;
import java.math.*;
import java.util.*;

public class Main {

	/*
 	 1789 problem
	*/
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		long num = Long.parseLong(br.readLine());
		long result =1;
		long count = 1;
		long add = 2;
		while(true) {
			if(num<count) {
				break;
			}
			result = add-1;
			count+=add;
			add++;
		}
		bw.write(String.valueOf(result));
		br.close();
		bw.close();
	}
}

---

주의

 

int형으로 하면 수 가 커서 에러가 납니다.

long타입을 이용해 줍시다.