1789 수들의 합

💡문제 분석 요약

• 서로 다른 N개의 자연수의 합이 S라고 한다. S를 알 때, 자연수 N의 최댓값은 얼마일까 ?
• 이때 중요한 건, 이 자연수 합의 최대값이 아니라 최대 "개수"를 구하는 것이다. 이거 잘못 읽어서 살짝 헤맸다.

💡알고리즘 설계

• 최대 "개수"라는 것에 주목해보자. 숫자가 많이 들어갈수록 이득이다. 그러므로 가장 작은 수부터 채워넣는 것이 이득이라는 소리.

💡코드

n = int(input())
i = 0

# 핵심 : 숫자들 합이 n을 만족시키는 최대 개수를 구하는 것
# 따라서, 가장 작은 수부터 채워나가는 것이 유리함 -> 0부터 한개씩 채워나감
# ex) 200이라는 값에 최대 몇개의 수가 들어가느냐? 200부터 0, 1, 2, ... 차례로 빼보면 됨.

while True:
    if n < i: # 만약 n = n-i 했을 때 i보다 작아지면, 이제 들어갈 숫자가 더이상 없는 상황임. = 이전까지가 최대값이라는 소리
        print(i-1) # 음수가 되기 직전의 값이 최대 개수를 의미
        break
    else:
        n = n-i # i = 0으로 초기화 한 후, n에서 차례로 빼줌
        i += 1 # i값을 1, 2, 3 ... 늘려감

💡시간복잡도

• i-1번만 실행시키면 끝난다. O(i-1) = O(i)

💡 틀린 이유

• 끝에서부터 빼는게 아니라 0부터 채워나가서 쉽게 못풀었다. 그래서 lst에 append하고, sum으로 n과 같은지 비교해서 len를 출력하려고 했다. 근데 생각보다 신경써야할 것이 많아 쉽게 못풀었던 것 같다.

💡 틀린 부분 수정 or 다른 풀이

• 0부터 더해가는게 아니라, n부터 빼가는 방식으로 풀이

💡 느낀점 or 기억할정보

• 문제를 잘 읽는 것이 제일 제일 중요하다. 문제 해석이 풀이 시작을 좌우한다.