[Python] 백준 풀기 1789 - 수들의 합

파이썬 백준 1789번

실버 5

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

1789번: 수들의 합

 

 

 

 

 

문제 보기

분류: 수학, 그리디 알고리즘

 

 

 

 

 

문제 풀기

가장 많은 N 개의 자연수를 얻기 위해서 가장 작은 1 부터 2, 3, ,,, 순서로 합을 시켜준다. 이때 S 를 넘게 되면 그 이전의 순차 자연수는 마지막 S 를 맞추기 위해 정확한 값으로 한 번 들어간다.

최대 N 을 위해 이런 식으로 진행된다는 의미이다.

 

 

코드 작성은 S 에서 1, 2, 3, ,,, 순차적으로 자연수를 빼주다가 S 가 음수가 되는 시점에 반복문을 빠져나오고 그때의 N 의 개수를 출력하는 식으로 작성하였다.

 

 

 

 

 

코드 보기

import sys
inputdata = sys.stdin.readline


def fnMaxN(S):
    N = 0
    i = 1
    while True:
        S = S - i
        if S < 0:
            break
        N += 1
        i += 1
    
    print(N)


if __name__ == "__main__":
    S = int(inputdata().strip())
    
    fnMaxN(S)



# 200
# 19

# 4294967295
# 92681

# 2147483648
# 65535