[그리디] 코딩테스트 문제 TIL (수들의 합) - 백준 1789번

1. 오늘의 학습 키워드

• 그리디 알고리즘

---

2. 문제: 1789. 수들의 합

• 단계: 🥈 실버 5단계
• 주제:
  • 수학
  • 그리디 알고리즘
• 출처: https://www.acmicpc.net/problem/1789

문제

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

입력

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

출력

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

예제 입력 1 복사

200

예제 출력 1 복사

19

---

3. 문제 풀이

Step1. 문제 이해하기

서로 다른 N개의 자연수의 합이 S라고 한다. S를 알 때, 자연수 N의 최댓값을 구하는 문제입니다.

즉, S라는 주어진 합을 초과하지 않으면서 최대한 많은 자연수를 포함하는 N을 찾는 것입니다.

입출력을 살펴보겠습니다.

• Input:
  • 첫째 줄에 자연수 S가 주어집니다.
• Output:
  • 자연수 N의 최댓값을 출력합니다.

Step2. 문제 분석하기

S라는 주어진 합을 초과하지 않으면서 최대한 많은 자연수를 포함하는 N을 찾는 것입니다.

따라서, 제일 작은 수부터 더하는 것이 전체 합 S을 만드는데 가장 많은 자연수를 포함합니다. 따라서 매 순간 가장 작은 숫자를 선택하므로 그리디 알고리즘 유형이라고 볼 수 있는 문제입니다.

예를 들어, $S = 200$일 때, 1부터 순차적으로 더하면 1, 2, …, 19까지 포함할 수 있습니다.

이 문제에서 그리디 알고리즘의 특징을 정리하자면 다음과 같습니다:

1. 탐욕적 선택: 가능한 가장 작은 자연수부터 더하는 선택을 반복합니다.
2. 단계별 최적화: 현재까지의 선택이 S에 도달하는 데 최적임을 보장합니다.
3. 전역 최적화 보장: 이 방식으로 계산한 N은 S에 대해 가능한 자연수 개수의 최댓값을 보장합니다.

Step3. 코드 설계

• 방법 1: 반복문을 통한 합산
  • N을 0으로 초기화하고, 합계 total도 0으로 초기화합니다.
  • 1부터 시작하여 N + 1을 더했을 때 total이 S를 초과하지 않는 동안, N을 증가시키고 total에 현재 값을 더합니다.
  • 반복이 끝나면 최종적으로 N은 가능한 자연수의 최댓값이 됩니다.
• 방법 2: 수학적 접근
  • 1부터 N까지의 합은 $total=\frac{N \times (N + 1)}{2}$입니다.
  • 이를 이용해 N을 구하는 방정식: $N(N+1)/2 \leq S$ $N^2 + N - 2S \leq 0$
    
  • 이 방정식을 풀어 N의 근을 계산하면: $N= \frac{-1 + \sqrt{1 + 8 \times S}}{2}$
    
  • 소수점을 버려 정수로 변환하여 $N$을 계산합니다.

Step4. 코드 구현

import sys
S = int(sys.stdin.readline().strip())
def sol(S):
    N = 0
    total = 0
    while total + N + 1 <= S:
        N += 1
        total += N
    return N
print(sol(S=S))

• 코드 설명:
  1. N과 total을 0으로 초기화.
  2. total + N + 1 <= S 조건을 만족하는 동안 반복:
     • N을 1 증가시키고, total에 추가.
  3. 반복 종료 시, N은 가능한 자연수 개수의 최댓값.
• 시간 복잡도: $O(\sqrt{S})$ – 합이 S를 초과하지 않는 가장 큰 N까지 반복.
• 결과:
  

import sys
import math
S = int(sys.stdin.readline().strip())
def sol(S):
    N = int((-1 + math.sqrt(1 + 8 * S)) // 2)
    return N
print(sol(S=S))

• 코드 설명:
  • N의 근을 계산하기 위해 방정식 $\frac{-1 + \sqrt{1 + 8 \times S}}{2}$를 풉니다.
  • math.sqrt를 사용해 제곱근을 계산.
  • 소수점을 버리고 정수로 변환하여 N 반환.
• 시간 복잡도: $O(1)$
• 결과:
  

---

4. 마무리

이번 문제는 자연수의 합 S를 구성하기 위해 가능한 가장 작은 자연수부터 차례로 더해나가 최대한 많은 자연수를 포함하는 N을 찾는 문제입니다. 이번 문제는 그리디 알고리즘으로 분류되며, 매 순간 가장 작은 자연수를 선택해 최적의 해를 보장하는 탐욕적 선택 속성을 활용한 문제입니다.

전체 코드는 다음 링크에서 확인할 수 있습니다.

글 읽어주셔서 감사합니다.