1789. [Python]수들의 합

1. 문제

 

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

1789번: 수들의 합

 

2. 접근 방법

 

• 시간 제한: 2초
• 메모리 제한: 128MB
• 수의 합 구하는 방법

 

3. 파이썬 코드

 

S = int(input())
s = S*2
n = int(1)

# 무한 반복문으로 제일 높은 n의 값을 찾음
while True:
# S*2 < n*(n+1) 한 이유는 1~N 까지 합을구하는 식이 n*(n+1)//2 이기 때문이다.
# s 값이 딱나누어 떨어지지 않는 경우 그 값을 딱 초과했을 때 break를 걸어준다.
# break 됐을때 count -1 해주는 이유는 값이 한개 더 더해졌기 때문에 빼줘야한다.
    if s < n*(n+1):
        print(n-1)
        break
# s 값이 같을때 break
    elif s == n*(n+1):
        print(n)
        break
    else:
        n += 1

 

4. 문제를 풀고난 후 생각

 

• 문제가 주어진 조건이 거의 없어서 이해를하는데 시간이 걸렸던 문제다.
• 문제에서는 합의 값이 주어지고 시작하며 이 합을 구하는 방법은 예전 초등학교때 1부터 10까지 합을 구하는 방법으로 1+10, 2+9, 3+8, 4+7, 5+6 => 11*5 처럼 10*11/2 '(n*(n+1)/2)' 식으로 구할 수 있다

예를 들어 10 이라는 합이 주어졌을 경우를 보면

1 + 2 + 3 + 4 = 10 으로 1,2,3,4의 합으로 나타낼 수 있다. 다른 방식으로 보면 '20 = n*(n+1) => n^2+n-20 = 0' 방정식의 값을 구해보면 (n+5)(n-4)로 n=4 가 나오며 4*5/2 = 10 이라는 값이 나오게 된다.

위를 보고 n의 값이 갯수가 되는 것을 이해했고 while True를 돌렸을때 특정값들에서는 잘 시행이 되다가 값이 안나올 경우 무한 루프를 돌아가 버리기때문에 s 값보다 커졌을때도 break를 걸어서 무한루프를 탈출 시키고 s 보다 값이 커졌다면 원하는 값을 구하는 갯수보다 +1이 된 것이기 때문에 -1을 해준 값을 출력해줬다.

 

5. 문제를 푸는데 도움이 되는 지식

 

• 그리디 알고리즘
• 가우스 덧셈