[백준] 1789번: 수들의 합 - 파이썬

📎문제링크: https://www.acmicpc.net/problem/1789

1789번: 수들의 합

 

💼서론

요즘 열심히 그리디 알고리즘 파고 있다. 🤸‍♂️
그리디 방법을 발견하면 뭔가 묘한 쾌감이 있다.

 

🧩문제 해석

서로 다른 자연수 N을 더한 값인 S가 주어졌을 때 N의 최대값을 구하는 문제!

 

📘풀이

1. N의 갯수를 최대로 만드려면 N은 1부터 시작해 N의 값을 +1 씩 증가하여 S를 만들면 그것이 N을 최대갯수로 만드는 것이다.

 

예제를 살펴보자!

200은 1+2+3+4+...+18+29 총 19개이다. 

1부터 18까지는 N이 하나씩 증가하였지만 마지막 값은 1증가한 값이 아니었다. 이 마지막 수 판단은 "서로 다른 자연수 N"이라는 문장에 키가 있다.

1부터 18까지 더한 값은 171이다. 여기서 그냥 진행하던대로 19를 더해버리면 190이 된다. 190이 200이 되려면 +10이 되어야 하지만 10은 이미 앞서 사용하였기에 다시 사용할 순 없다. 즉 그래서 19를 더하지 않고 바로 남은 값들을 더하였다. 

200에서 1부터 차감한 값:

n       n      i

200 = 200 - 0

199 = 200 - 1

197 = 199 - 2

194 = 197 - 3

190 = 194 - 4

.

.

.

29 = 47 - 18

10 = 29 - 19

-10 = 10 - 20(?)

문제가 되는 부분을 잘 살펴보면 i가 n보다 클때 오류가 발생하였다!

즉 i가 n보다 크거나 같을때까지 n = n-i를 수행하면 된다!

 

 

💻코드

n = int(input())
i = 0
cnt = 0
while True:
    if n > i: # n이 i보다 크면 n에 i를 차감
        i += 1
        n = n-i
        cnt += 1
    else:
        print(cnt)
        break