1789 수들의 합

1. 문제

문제는 링크에 들어가면 있다.

2. 정답 코드

문제의 내 정답 코드는 다음과 같다.

import sys
read = sys.stdin.readline

S = int(read())

if S == 1 :
    print(1)
else :
    summation = 0
    array = []
    for i in range(1,S):
        summation += i
        if summation > S :
            summation -= i
            break
        array.append(i)

    print(len(array))

3. 문제 풀이

이 문제는 꽤나 재밌는 문제였다. 입력받은 S를 서로 다른 자연수들로 더해서 만들때, 자연수들의 개수 N을 최대로 만드는 문제이다. 자연수들의 개수를 최대로 만들려면 작은 수들을 많이 더할수록 개수가 늘어날 것이라고 생각했다. 그래서 1부터 시작해서 모든 값들을 다 더해가면서 summation보다 S의 값이 더 커지게 되면 반복문을 종료한다. 이때, 만약 값이 더 커지면 제일 마지막(큰) i보다 큰 수가 더해질 일이 없다. 즉, 예를 들면 55을 입력으로 넣으면 1~10까지의 합인데, 56을 넣으면 1~10까지 더하고 1이 남게 된다. 10을 넘지 못하는 것이다. 그럼 이 남은 1을 그냥 마지막 수 10에 더해주면 된다고 생각했다. 같은 방법으로 65를 넣게되면 1~10까지 더하고 10이 남게 될텐데 이 남은 10을 1로 10개를 만들어서 1~10까지 하나씩 더해주게 되면 N을 최대로 유지하면서 옆으로 한칸씩 shift하는 느낌을 가질 뿐이다.