[그리디 알고리즘 Lv.03] 1789번 수들의 합 (Python)

 

1. 문제

    1789번 수들의 합 (https://www.acmicpc.net/problem/1789)

 

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

 

 

2. 문제 포인트

• 중복되지 않는 자연수 개수 구하기

 

반응형

 

3. 접근법

• S를 자연수로 하나씩 빼면서 총 개수를 구한다
• 1, 2, 3... 숫자 하나씩을 S에서 빼면서 계산하다가 뺄 수(n)보다 S의  나머지가 작은 경우 반복문을 종료한다.
  ex. 15인 경우
         15 - 1 - 2 - 3 - 4 - 5  = 0  >> 5번
         17 - 1 - 2 - 3 - 4 - 7 = 0  >>  5번
           - 1~5까지 빼면 17은 2가 남게 됨
           - 1~4까지 빼고 7을 빼면 중복되지 않은 자연수들로 계산이 가능

 

4. 결과 코드

import sys

a = int(sys.stdin.readline().strip())

# 숫자 사용 횟수
cnt = 0
# 계산에 사용될 숫자
num = 1

while True:
    # 입력받은 숫자에서 1부터 하나씩 빼서 숫자 사용 횟수 계산
    a -= num
    cnt += 1
    num += 1

    # 1부터 1씩 증가한 num이 a의 나머지값보다 크면 숫자가 중복되어 사용되기에
    # num이 a보다 크게 되는 경우 루프 종료
    if num > a:
        break

print(cnt)

# 1789번 수들의 합
# https://www.acmicpc.net/problem/1789