BAEKJOON_1789 "수들의 합" PYTHON

[백준] 1789번 Python 파이썬

 

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

1789번: 수들의 합

이 문제에서 N의 최대값을 구하려면 작은 수들을 더하여 S를 만들어야한다.

 

s를 입력받아 s가 1인 경우와 1이 아닌 경우로 나누어 문제를 해결하였다.

아래 코드의 경우 시간 복잡도가 O(sqrt(s)) 이고, 입력이 클 수록 복잡도가 증가한다.

s = int(input())
result = 0

for i in range(1, s + 1):
    if s == 1:
        result = 2
        break
    else:
        s -= i
        result += 1
        if s < 0:
            break
print(result - 1)

다른 풀이들을 보니 1부터 n까지의 합을 구하는 공식인 'n(n+1)/2' 를 이용하여 해결하였다.

이 경우 시간 복잡도는 O(1)로 입력과 상관없이 최적의 시간 복잡도를 갖는다.

 

코드는 아래 블로그에서 확인하였다.

 

https://dev-scratch.tistory.com/m/20

[Python] 1789 수들의 합

 

혼자 공부하며 올리는 블로그입니다. 틀린 내용은 댓글 남겨주시면 감사하겠습니다.