[백준_1789번] 수들의 합

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

1789번: 수들의 합

[문제]

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

 

[입력 조건]

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

 

[코드]

import java.util.*;

public class BaekJoon_1789 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		long s=sc.nextLong();
		
		long start=1;
		long end=s;
		long result=0;
		
		while(start<=end) {
			long mid=(start+end)/2;
			
			// 1부터 mid까지의 합 구하기
			long sum=(mid*(mid+1))/2;
			
			// 합이 s보다 크다면 작은 범위 탐색
			if(sum>s) {
				end=mid-1;
			}
			
			// 합이 s보다 작다면 mid 값 저장 후, 더 큰 범위 탐색
			else {
				start=mid+1;
				result=mid;
			}
		}
		
		System.out.println(result);
	}

}

 

[고찰]

 이번 문제는 s의 범위가 굉장히 크다는 것을 보고 이진탐색을 사용해야 한다는 것을 알았다. 서로 다른 N개의 자연수를 선택하여 자연수 S를 만들때 많은 수를 선택하기 위해서는 1부터 N개를 더해야 한다. 그리고 이 중 가장 큰 값은 N이 될 것이다. 따라서 이진탐색을 통해 1~mid 까지의 합을 구하고, 합의 결과에 따라 범위를 조정해가는 방식으로 해결할 수 있다.

 처음에는 for문을 사용하여 1~mid 까지의 합을 구했지만 시간초과로 실패해 수학 공식을 사용하여 구했고, 모든 변수는 long 자료형을 사용하지 않아 몇번의 시행착오를 겪은 문제였다.