[BOJ 1789, Python 3] 수들의 합

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

1789번: 수들의 합

 

 

풀이

 

서로 다른 N개의 자연수들의 합으로 S를 만들 수 있는 N의 최댓값을 구하라고 한다.

그러면 1 + 2 + 3 + 4 + ...로 하는 아이디어를 생각할 수 있다.

그런데 이렇게 더해보면 운 좋으면 S를 만들 수도 있지만, 못만드는 수가 대부분이다.

 

여기서 마지막 x개의 자연수를 한 칸씩 오른쪽으로 끌어당겨서 수를 만드는 방법을 생각할 수 있다.

그니까 예를 들어서 만약 S = 14라면 1 + 2 + 3 + 4 = 10이고, 1 + 2 + 3 + 4 + 5 = 15이다.

그런데 (1 + 1) + (2 + 1) + (3 + 1) + (4 + 1)로 14 - 10 = 4이니 4개의 수를 오른쪽으로 한칸 이동시켜서 2 + 3 + 4 + 5 = 14로 만들 수 있다.

 

아니면 쉽게 부족한 값만큼 마지막 수를 큰 수로 바꾼다고 생각하면 된다. S = 14일 때 1 + 2 + 3 + 4에서 4+4로 바꾸어서 1 + 2 + 3 + (4 + 4) = 14로 하면 된다.

 

코드

코드는 1부터 N까지의 수들의 합이 N * (N + 1) / 2이므로 대충 for문을 1,000,000 까지 돌리다가 break문을 사용하게 만들었다.

x = int(input()) * 2
ans = 0
for i in range(1, 1000000):
    ans = i * i + i
    if ans >= x: break
print([i - 1, i][ans == x])