1789 수들의 합

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

1789번: 수들의 합

 

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




public class Main {

	  public static void main(String[] args) throws IOException {

		  
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		long N = Long.parseLong(br.readLine());
	
		for(long i=1; i<=N;i++) {
			long sum = i*(i+1)/2;
			if(sum >= N) {
				
				if(sum > N) {
				System.out.println(i-1);
				break;
				
				} else if (sum == N) {
					System.out.println(i);
					break;
				}
				
				
			}
			
		
				
			}
		}
	  }

일단, 서로 다른 자연수이면서 제일 많은 수를 합해서 예제입력에 나온대로 200을 만들기 위해서는

1+2+3+4+5+ .. =200

 

이렇게 1부터 순서대로 계속 더해나가야 한다.

이래야 가장 많은 수를 합해서 200을 만들 수 있다.

이때 1부터 n까지의 합은 n*(n+1)/2 로 나타낼 수 있다.

 

그런데 여기서 1부터 n까지 더해서 절대 200을 만들 수 없다.

1+2+3+ .. +19 = 190

1+2+3+ .. + 20 = 210 

 

이기 때문이다.

그런데 이 경우는 문제에서 19를 출력하라고 나와있다.

합이 200을 초과하지 않게 하는 최대 자연수를 출력해야 하기 때문.

 

그래서 코드에서도 만약 sum>=N이라면 즉, 210>=200 이기 때문에

이 경우의 i=20 이라, 그보다 하나 작은 수인 i-1=19를 출력하라고 했다.

 

 

* 주의 1)

위의 경우 변수를 double, int 형으로 받았더니 시간초과가 났다.

for문 내 i도 long 형으로 받아야 시간초과가 나지 않는다.