• 현재 상황에서 지금 당장 좋은 것만 고르는 방법
• 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력 요구
• 정당성 분석이 중요 - 단순히 가장 좋아 보이는 것을 반복적으로 최적해를 구할 수 있는지 검토해야 한다!
• 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 이를 추론할 수 있어야 풀리도록 출제됨

문제 : 거스름 돈

• 가장 큰 화폐 단위부터 돈을 거슬러 준다
• 가장 먼저 500원 만큼 거슬러줄수있을 만큼 거슬러준다
• 100원, 50원, 10원..차례로 거슬러준다
• 정당성 : 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문
  • ex ) 800원을 거슬러 주어야 할 때, 500원, 400원, 100원으로 거슬러주어야 한다면 가장 큰 단위부터 거슬러 줄 때 최적해가 나올 수 없음. 500원1개 + 100원3개가 아닌 400원*2개가 최적해이기 때문
• 문제 풀이를 위한 최소한의 아이디어를 떠올리고, 이것이 정당한지 검토할 수 있어야 한다.

시간 복잡도

화폐단위의 종류가 k라고 할 때, 시간 복잡도는 O(k)

거슬러줘야 하는 금액과 시간복잡도는 무관하다!

문제 : 1이 될 때까지

• 어떤 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다. 단 두번째 연산은 N이 K로 나누어 떨어질 때만 선택할 수 있습니다.
  1. N에서 1을 뺍니다
  2. N을 K로 나눕니다.
• N이 17, K가 4라고 가정할 때, 1번의 과정을 한 번 수행하면 16이 되고, 2번의 과정을 두 번 수행하면 N은 1이 된다. 최소 실행 횟수는 3이 된다.
• 과정을 수행해야 하는 최소 횟수를 구하는 프로그램을 작성하시오.

해결 아이디어

• 가능하면 최대한 많이 나누는 방법
  • 1을 뻬고 나누는 것이 아니라, 일단 나눠준다
• N이 아무리 큰 수여도, K로 계속 나눈다면 기하급수적으로 빠르게 줄일 수있다.

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

cnt = 0
while True:
    target = (n // k) * k  # k로 나누어떨어지는 수 만들기
    cnt += (n-target)  # 이만큼 1을 빼줌
    n = target
    if n < k:  # 더 이상 나눌 수 없을 때 빠져나옴
        break
    cnt += 1  # k로 나눈 횟수 더하기
    n //= k  # n을 k로 나눔

cnt += (n-1)  # n < k 일때 빠져나왔으므로 1이 될때까지 1을 빼준 횟수 더하기
print(cnt)

문제: 곱하기 혹은 더하기

• 두 수 중에서 하나라도 0 혹은 1인 경우 더하기
• 그 외의 경우 곱하기 수행

s = list(map(int, input()))
ans = s[0]

for i in range(1, len(s)):
    num = s[i]
    if num <= 1 or ans <= 1:
        ans += num
    else:
        ans *= num

print(ans)

문제 : 모험가 길드

나의 풀이 (틀린 풀이!)

n = int(input())
arr = list(map(int, input().split()))
arr.sort()

cnt = 0
i = 0
while True:
    if len(arr) == 0 or len(arr) < arr[i]:
        break
    end = arr[i]
    del arr[:end]
    cnt += 1

print(cnt)

• 반례)
  • 입력이 5 / 100 2 2 3 3 인 경우
  • 정답은 [2, 2] 팀 하나이지만, 위 코드 실행 결과 2가 나오게 되어 틀림

정답 예시

n = int(input())
arr = list(map(int, input().split()))
arr.sort()

ans = 0  # 그룹 개수
cnt = 0  # 현재 그룹에 포함된 모험가의 수
for i in arr:
    cnt += 1  # 현재 그룹에 포함시키기
    if cnt >= i:  # 그룹 멤버가 현재 모험가의 공포도 이상
        ans += 1  # 그룹 결성
        cnt = 0   # 멤버 수 초기화

print(ans)