백준 1789번: 수들의 합

백준 1789번: 수들의 합

1789번: 수들의 합

- 이분 탐색을 활용하여 풀면 되는 전형적인 문제이다.

• start = 1, end = s(입력받은 수)
• mid = (start + end) // 2
• 만약 (mid * (mid + 1) // 2) 가 s보다 작거나 같으면 answer에 mid를 저장하고 이분탐색을 계속 이어 나간다. 참고로, 여기서 (mid * (mid + 1) // 2) 는 1부터 mid까지의 합이다. 
• 만약 (mid * (mid + 1) // 2) 가 s보다 크면 end = mid - 1 로 하여 mid 값을 줄인다.
• start가 end보다 작거나 같을 때까지 while문을 돌려서 answer의 최댓값을 구한다.

아래는 파이썬 코드이다.

 

	s = int(input())
	start = 1;
	end = s
	while start <= end:
	mid = (start + end) // 2
	if mid * (mid + 1) // 2 <= s:
	answer = mid
	start = mid + 1
	else:
	end = mid - 1
	print(answer)

view raw BOJ_1789.py hosted with ❤ by GitHub