[코테/백준] Python 수들의 합 - 1789번

실패 | 시도 - 번

 

🔗 [백준] 1789번 수들의 합

1789 : [그리디 알고리즘] 수들의 합(py)

---

문제 설명

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

---

문제 분석

- N이 커지기 위해서는 작은 자연수들의 합이어야 한다. 또 서로 다른 자연수이기 때문에 작은 수들을 차례대로 세워서 합을 구해야 한다. 즉 공차가 1인 등차수열 형태가 나온다. 

- 등차수열의 공식을 이용하였다. (사실 등차수열 공식을 까먹어서 공식을 찾아보기도 했었다...)

• 등차수열의 합 : $$ \frac{n{\{2a+(n-1)d}\}}{2} $$
• n 구하기 : a₁ = 1, d = 1, 등차수열의 합 = 200 → 전개 : n(n+1) = 400

→ 자연수를 얼만큼 더해야 200이 되는지 알려면 n을 알아야 하며 n은 곧 더한 자연수의 개수가 된다. 등차수열의 합을 전개하면 n(n+1) = 400가 되며 대략적인 n을 구하기 위해 제곱근을 사용했다. 400의 제곱근은 20이다. (n ≒ 20)

 

- 1부터 20까지의 등차수열의 합은 210이어서 200을 넘는다. 20보다 작은 수 19까지의 등차수열의 합은 190이다. 그렇다면 자연수 N의 최댓값은 19가 될 수 있다.

• 1부터 20까지의 등차수열 합 : 210 
• 1부터 19까지의 등차수열 합 : 190

 

- 1부터 19까지의 등차수열 합이 190이기 때문에 200으로 억지로 만들어주면 된다. 200을 만들어주기 위해 한 숫자만 바꾸면 되고 결론적으로 자연수의 개수는 변하지 않는다. 

• 원래 : 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19  → 190 (10이 모자름)
• 변경 : 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 29  → 200
• 원래의 개수와 변경후의 개수는 모두 19개이다. 

---

입력

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

---

출력

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

---

입력과 출력 예시

입력	출력
200	19

 

---

내 소스

• 첫시도 : 실패 (문제의도 이해실패)

import math
n = int(input())
a = int(math.sqrt(n*2))
expect = a * (a + 1) / 2
if (expect > n):
    result = a-1
else:
    result = a
print(result)

 

소스 설명

import math
n = int(input())
a = int(math.sqrt(n*2))

[1 - 3] : 등차수열의 합 공식에 따라 n * 2의 제곱근을 변수 a에 저장한다.

 

expect = a * (a + 1) / 2
if (expect > n):
    result = a-1
else:
    result = a

[4 - 8] : 변수 expect에 a에 대한 등차수열의 합 공식을 적용한 값을 저장한다. expect가 n보다 크면 result에 a-1을 저장하고 expect가 n보다 작거나 같으면 result에 a를 저장한다. 

---

다른 코드 분석

- for문을 사용해서 자연수 합 S에 근접할 때까지의 개수를 센다.

- 등차수열의 합 공식을 사용해서 답을 구하기도 했다. (while 문 사용)

---

회고

- 문제를 너무 복잡하게 생각했던 것 같다. 자연수의 최대 범위가 42억이다 보니 for문을 사용하지 않으려고 애썼다.

---

Ref. 

1. 등차수열 공식 / https://calcproject.tistory.com/448

2. 문제 풀이 / https://kongpowder.tistory.com/41

3. 문제 풀이 / https://pacific-ocean.tistory.com/80

4. 문제 풀이 / https://konghana01.tistory.com/53

---

* 잘못된 부분에 대해 댓글 남겨주시면 감사하겠습니다! 😀