[Python] 백준 1789번: 수들의 합

그리디 알고리즘 문제

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

• S를 만드는 서로 다른 N개의 수의 최대 개수 구하기

1차 시도

import sys
input = sys.stdin.readline
#S(1 ≤ S ≤ 4,294,967,295)
s = int(input())
# 1~n 까지의 합 n*(n+1) //2 를 이용
answer = 0
for i in range(int((2*s)**0.5), 1, -1):
    sum_i = i*(i+1)//2
    if s - sum_i > i:
        answer = i
        break
# 1~i까지의 합 + i보다 큰 수 한개를 더한값이 s일 때 N이 최대
print(answer+1)

• S보다 작은 1~n까지의 합(sum_i)을 만드는 n + 1 (n보다 큰 한개의 수)이 최대값이라고 생각하고 for문 작성

반례

입력 3
출력 1
답 2

2차 시도

import sys
input = sys.stdin.readline
s = int(input())

i = int((2*s)**0.5)
a = s - (i * (i+1)//2)

while a<i:
    if i * (i+1) > s:
        i-=1
    a = s - (i * (i+1))//2
print(i+1)

• while 문으로 변경 a(추가로 더할 숫자)가 i보다 클 때까지 i를 줄임

반례

입력 5
출력 3
답 2

• a==i일 경우 답이 아님 + while을 a<=i로 할 경우 무한루프

통과 코드

import sys
input = sys.stdin.readline
s = int(input())

i = int((2*s)**0.5)
a = s - (i * (i+1)//2)
while a<i:
    if i * (i+1) > s:
        i-=1
    a = s - (i * (i+1))//2

if i==a:
    print(i)
else:
    print(i+1)

• i==a일 경우, 앞의 수 하나를 제외하고 a'를 만든다고 생각하고 i를 출력
• 그 외 i개 + 1개(a)로 출력