백준 2839

 

#2839
n = int(input())
answer = 0
while n >= 0:
    if(n % 5) == 0:
        answer += (n // 5)
        print(answer)
        break
    n -= 3
    answer += 1
else:
    print(-1)

 

 

처음에는 이 문제를 노가다로 풀려고 했는데 줄이 너무 길어져서 다시 고민했다.

힌트를 얻기 위해 검색하던 중, 이 문제가 그리디 알고리즘이라는 것을 알게 되었다.

"그리디 알고리즘"은 잔돈 거슬러 주기에서 많이 쓰이는 알고리즘이라고 한다.

 

코드의 풀이를 하자면,

 

n을 입력 받은 후, n이 가장 큰 수인 5로 나누어진다면 바로 답을 구하고, 그렇지 않으면 -3을 해줌으로써, 3으로 한 번 나누어졌다고 생각할 수 있으므로 answer에는 1을 더해준다.

이런 식으로 계산이 계속 돌아가면 5로 몇 번 나누어졌는지와 나누어지지 않았을 때 3으로 나누게 된 수를 그대로 answer에 담을 수 있으므로 쉽게 풀리게 된다.

 

코딩은 할 수록 많은 새로운 부분을 알게 되어 복잡하고 어렵지만, 또 해결하면 이렇게 간단했나 싶은 생각이 든다.

여하튼 어렵다는 거