(Python/🥈4)백준 알고리즘 1789번: 수들의 합

수들의 합

 

문제 바로가기 

 

문제:

서로 다른 N개의 자연수의 합이 S라고 한다. S를 알 때, 자연수 N의 최댓값은 얼마일까?

입력:

 

첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다.

출력:

첫째 줄에 자연수 N의 최댓값을 출력한다.

 

풀이:

 

import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')


N = int(sys.stdin.readline())
res = 0
cnt =0
for i in range(1,N+1):
    res += i
    cnt += 1
    if res > N:
        cnt -=1
        break

print(cnt)

 

최솟값을 구하려면 1 부터 쭉 더해서 누적합이 N보다 커지면 카운한 갯수에서 1을 빼주고 브레이크 해준다.

이유는

만약에 

1 2 3 = 6

1 2 4 = 7

1 3 4 = 8

2 3 4 = 9

1234 = 10

 

 

이런식으로 123과 1234 의 차이는 4 지만 그 안에 6부터 10 사이인 수들을 다 표현이 가능하다.

 

즉 cnt가 i 와 i+1 사이의 값들을 i+1개중 i 개로 표현이 가능하다. 그럼 res 가 N이 넘어가는 시점에 cnt 를 -1 해주면 그걸로 표현이 된다.

 

예를들면

 

N = 200 이면

1 ~19 는 190이고 1 ~ 20 은 210이다

cnt 19 = 190 cnt20 = 210인 셈인것이다.

그럼 190 과 210 사이는 1부터 20 사이의 숫자 19개로 표현이 가능하다.