백준 1789번 -python

그리디 알고리즘

n=int(input())
county=1
sum=0
result=0
while 1:
    if not(n >=county) :
        break
    n=n-county
    county+=1
    result+=1
print(result)

이번 문제는 입력된 정수를 값으로 하는 1~n의 수를 조합한 덧셈식 중 가장 조합한 식의 수가 많은 식을 찾는 문제였다. 해당 문제는 가장 좋을 때를 생각해 보았을 때, 1부터 차근차근 빼나가는 것이 가장 좋은 방법 일 것이다. 그렇기 때문에 하나씩 빼나가면서 해당 값에 결과값을 찾아 나갔다. 그렇게 되면 마지막 남은 수는 n의 수보다 작아지게 된다. 이 경우에는 이미 최대한으로 덧셈식을 늘린 경우이다. 그 나머지 부분은 앞에 덧셈식에 잘 더해준다고 생각해주고 제오 해주면 된다. 따라서 그 나머지 부분을 제외한 앞에 썻던 덧셈식의 수가 답이된다.