백준 1789 파이썬(그리디)

처음엔 문제를 이해하는것부터 난해했다.

도데체 무슨말인가?? 

S와 N이 한번에 머리속에서 정리되지는 않았다.

한참을 곰곰히 생각하다가

입력받은 수(S)를 만들어주기 위해서 최대로 많이 필요한 서로다른 숫자가 몇개(N)인지? 

이걸 물어보는 문제였다. 

 

그리디(greedy)문제이므로

최대한 많은 숫자를 사용하려면 자연수 중 제일 작은 수인 1부터 더해나가는 것부터 생각을 해보았다.

그리고 더할 만큼 더한뒤에 입력받은 숫자를 맞춰주는 수를 찾아서 넣어주고 그 숫자들의 개수를 카운팅하면 되겠다는 생각을 하였다.

 

처음 시도한 코드에서는 시간초과가 떳다.

시간복잡도가 O(n^2)가 될 것같다.

sum_num 에서 반복 한번

그리고 while문에서 반복 한번이 겹쳐서 실행이 되었으니...

다른 방법을 생각해봐야 한다.

# 1789 수들의 합 - 그리디

n = int(input())

def sum_num(n):
    sum = 0
    for i in range(1,n+1):
        sum += i
    return sum
i = 0
while True:
    if n <= 2:
        print(1)
        break
    i += 1
    if sum_num(i) + i+1 + i+2 > n:
        print(i+1)
        break

 

그래서 반복문을 하나 빼줄 수 있는 방법이 없을까 생각해보았다.

조금만 더 생각해보니 훨씬 짧고 쉬운 방법이 있었다.

# 1789 수들의 합 - 그리디

n = int(input())

i = 0
while True:
    if n <= 2:
        print(1)
        break
    i += 1
    n -= i
    if n < i+1 + i+2:
        print(i+1)
        break

맞았다!!

 

알고리즘 문제를 풀면서 느끼는 것은

내가 스스로 문제자체를 어렵게 만들고 나도모르게 고수(?)처럼 뭔가 있어보이는 코딩을 짜고싶어 한다는 생각이 들었다.

지금은 이것보다는 어떻게 하면 내가 컴퓨터가 작동하는 방식을 이해하고 그 과정을 구현할 수 있을지를 더 고민해봐야겠다.