탐욕법

탐욕법 또는 그리디 알고리즘이라고 불리는 알고리즘 방식은 해당 상황에서 당장 좋은것을 고르는 방법이다. 일반적으로 탐욕법은 최적의 해를 보장할 수 없는 경우가 많다. 탐욕법으로 문제를 해결 하려 한다면 문제 해결 아이디어의 정당성을 검증해야 올바르게 문제를 해결 할 수 있다.

위문제에서 최적의 해는 21이다.
위 문제를 탐욕법으로 풀면 잘못된 해를 구하게 된다.
노드5에서 바라보는 가장큰 값 -> 10
노드10에서 바라보는 가장큰 값 -> 4
5 + 10 + 4 = 19

그리디 문제

어떤 수를 1이 될 때까지 최소 횟수로 N에서 1을 빼거나 K로 나누어 주는 문제이다.
입력 조건을 보면 K가 항상 2이상인것을 알 수 있다. K가 1이하의 숫자가 아니기때문에 나누는게 N을 빠르게 줄일 수 있을것이다. 나누는게 유리하기 때문에 나누는 것을 선택하되 그럴 수 없는 경우 1을 빼주는 방식으로 해결하면 된다.

n, k = map(int,input().split())

result = 0

while True:
	# n을 k로 나눈 몫을 k에 곱해 n이 몇이여야 나누어 떨어지는지 알아낸다
	target = (n // k) * k
	# n - target으로 1을 뺴는 과정을 결과에 더한다
	result += (n - target)
	# target으로 다시 반복
	n = target
	# n이 k보다 작아지면 반복문 탈출
	if n < k :
		break
	result += 1
	# n이 1이될때까지 k로 나눈다 
	n //= k

result += (n - 1)
print(result)

adventurer = int(input())
fear = list(map(int, input().split()))
# 오름차순 정렬으로 작은 공포도를 가진 모험가부터 파티를 결성한다.
fear.sort()
# 총그룹의수
result = 0
# 현재 그룸에 포함된 모험가의 수
count = 0

for i in fear:
	count += 1
	if count >= i:
    # 현재 그룸에 포함된 모험가의 수가 현재의 공포도 이상이면 파티결성
		result += 1
		count = 0

print(adventurer)