[Python_Greedy] 백준 1789번 : 수들의 합

1. 문제

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

1789번: 수들의 합

 

 

 

 

2. 풀이 과정

1~n까지의 합 = n(n+1)/2 이므로 n(n+1)/2 ≤ (입력값)을 만족하는 n의 최댓값을 구하면 된다.

 

n(n+1)/2 ≤ (입력값) => n(n+1) ≤ 2*(입력값)이다.여기서 n(n+1)은 n*n < n(n+1) < (n+1)(n+1)을 만족한다.

모든 항에 루트를 씌우면, n < ${(n(n+1))}^.5$ < n+1이 된다.

 

int형으로 바꾸면 소수점을 버리니 n을 반환할 수 있으며, ${(n(n+1))}^.5$ ≤ 2*(입력값)이므로 n+1을 반환할 수도 있다. 따라서 나온 결과값이 n인지 n+1인지만 구분하여 출력해주면 된다.

 

import sys
input = sys.stdin.readline

n = int(input())
su = int((2*n)**.5)

if su*(su+1) <= 2*n:
  print(su)
else:
  print(su-1)