백준 1789번: 수들의 합

문제 설명

• 최대한 많은 자연수를 더해 S를 만들어야 합니다

접근법

• 서로 다른 N개의 자연수를 더해 만들 수 있는 가장 작은 S는 1+2+3...+N을 한 N*(N+1)/2입니다.
  • 그렇기 때문에 N개의 자연수로는 N(N+1)/2부터 무한대까지의 수를 만들 수 있습니다.
  • 하지만 1+2+3..+N+(N+1)을 한 (N+1)(N+2)/2는 N개로 만들 수도 있지만 N+1로도 만들 수 있습니다.
  • 즉 숫자 S를 표현하는 가장 큰 N은 N(N+1)/2<=X<(N+1)(N+2)/2의 범위를 가집니다.
• 예시
  • 5는 [1,4],[2,3]로 만들 수 있습니다
  • 6은 [1,5],[2,4]로 만들 수 있지만 [1,2,3]으로 만드는 게 N이 더 큽니다
  • N=4로 만들 수 있는 가장 작은 수는 [1,2,3,4]를 사용해서 만든 10이기 때문에 7,8,9는 3개의 자연수로 만드는 것이 최선입니다.

정답

x=int(input())
for i in range(100000): # S의 범위를 포함할 수 있는 충분히 큰 i를 설정합니다
    if i*(i+1)/2<=x<(i+1)*(i+2)/2:
        print(i)
        break

기타

• 1부터 직접 값을 넣는 방법 말고 i(i+1)/2<=x<(i+1)(i+2)/2를 만족하는 i를 구할 수 없을까?
  • 현재로써는 어떤 방법이 있는지 모르겠음