[BOJ/BaekJoon] 백준 1789 수들의 합 (Python / 파이썬)

BaekJoon BOJ 백준 1789 수들의 합 문제는 서로 다른 N개의 자연수의 합이 S라고 하고 S를 알 때, 자연수 N의 최댓값을 구하는 문제이다. 그리디 알고리즘 유형의 문제로 난이도는 Silver 5이다.

 

BaekJoon 1789 수들의 합 문제 정보

출처

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

알고리즘 분류

- 그리디 알고리즘, 수학 (greedy algorithm, 탐욕법)

난이도

- 실버 5 / Silver 5

 

수들의 합 문제 요약

• 서로 다른 N개의 자연수의 합이 S라고 한다.
• 첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다.
• S를 알 때, 자연수 N의 최댓값을 구하여 출력한다.

문제 풀이 과정

작은 자연수들이 많을수록 N이 커진다. 주어진 수에서 1부터 증가시키며 빼간다. 뺄 때마다 카운트한다.

빼는 수가 남은 수보다 크거나 같으면 중단한다.

 

ex) 8 = 1 + 2 + 5

8 - 1 = 7  -> 빼는 수 1 < 남은 수 7

7 - 2 = 5  -> 빼는 수 2 < 남은 수 5

5 - 3 = 2  -> 빼는 수 3 >= 남은 수 2

 

1. 자연수의 합 S를 입력받는다.
2. S가 0이 아닌 동안에
3. S에서 1부터 증가시키며 빼간다. 뺄 때마다 카운트한다.
4. 빼는 수가 남은 수보다 크거나 같으면 중단한다.
5. 카운트한 수를 출력한다. 

 

코드 및 설명

• S - 자연수의 합
• i - 빼는 수
• cnt - 합한 자연수의 개수

S = int(input())

i = 1  # 빼는 수
cnt = 0
while S != 0:
    S -= i
    cnt += 1
    if S <= i:  # 남은 수 <= 빼는 수
        break
    i += 1

print(cnt)

---

 

BaekJoon 백준 BOJ 1789 수들의 합 문제를 파이썬 python으로 풀어보았다. 난이도는 Silver 실버 5이다.