[Algo] 그리디(탐욕) 다시 보면 좋은 문제 모음집!

오른쪽 문제를 클릭하면 해당 문제를 볼 수 있습니다.

1. 백준 - 거스름돈

소요시간: 25분
난이도: 하

def sol(n):
    tmepN = n
    div5 = n // 5
    while True:
        if div5 > 0:
            tmepN -= div5 * 5
        div2 = tmepN // 2
        tmepN -= div2 * 2
        if tmepN == 0:
            return div2 + div5
        if div5 == 0 and tmepN != 0:
            return -1
        if div5 > 0:
            div5 -= 1
        tmepN = n

print(sol(int(input())))

2. 백준 - 뒤집기

소요시간: 30분
난이도: 하

def sol(s):
    cnt = 0
    for i in range(1,len(s)):
        if s[i-1] != s[i]:
            cnt += 1
    if cnt % 2 == 0:
        return cnt // 2
    else:
        return (cnt + 1) // 2

s = list(input())
print(sol(s))

3. 백준 - 등수매기기

소요시간: ??분/시간초과가 계속 뜬다....왜지.. -> pype3로 하면 통과
난이도: 하

n = int(input())
arr = [int(input()) for _ in range(n)]

ans = 0
arr.sort()
for i in range(len(arr)):
    ans += abs(arr[i] - (i + 1)) 

print(ans)

4. 백준 - 배

소요시간: ??분/pypy3으로 해야함
난이도: 중

• 단순히 박스의 무게와 크레인의 무게 제한을 오름차순으로 정렬 후 문제를 해결하다가 계속 틀렸다는 것을 깨달았다. 왜 계속 오름차순 정렬에만 집착을 했니 과거의 나 자신. 내림차순도 있다고!!예를들어,
  - 내림차순 정렬
  크레인 무게 제한: 9 8 6
  박스의 무게: 9 9 4 2 2
  이 경우 2분 소요.
  - 오름차순 정렬
  크레인 무게 제한: 6 8 9
  박스의 무게: 2 2 4 9 9
  이 경우 3분 소요
  이처럼 내림차순으로 해야 최적의 해를 가질 수 있다.

ans = 0
n = int(input())
weight_limit = list(map(int,input().split()))
m = int(input())
weight = list(map(int,input().split()))

weight_limit.sort(reverse=True)
weight.sort(reverse=True)

if max(weight) > max(weight_limit):
    print(-1)
    exit()

while len(weight) > 0:
    ans += 1
    for w in weight_limit:
    	if len(weight) == 0: #사실 필요없는 부분. len(weight)가 0이면 for문이 실행되지 않기때문
            break
        for i in range(len(weight)):
            if weight[i] <= w:
                del weight[i]
                break
print(ans)

#틀린 코드
weight_limit.sort() # 틀린 이유: 내림차순을 고려하지 않음!
weight.sort()

if max(weight) > max(weight_limit): # 틀린 이유: 문제 조건 -1 출력 상황도 놓침 - 뒤늦게 캐치
    print(-1)
    exit()
    
while len(weight) > 0:
    ans += 1
    for w in weight_limit:
        if weight[0] <= w: #틀린 이유: 첫번째꺼가 수용이 안되면 다음꺼가 기회를 가질 수 있어야한다
            del weight[0]
            if len(weight) <= 0:
                break
print(ans)

5. 백준 - 센서

소요시간: 한시간
난이도: 하 (권장 소요 시간 30분)
O(nlogn)

n = int(input())
k = int(input())

if k >= n: #놓친부분
    print(0)
    exit()
    
arr = list(map(int,input().split()))
arr.sort()

dist = []
for i in range(1,n):
    dist.append(arr[i] - arr[i-1])

#dist를 정렬했을때
dist.sort(reverse=True)

print(sum(dist[k-1:]))

#dist를 정렬하려고 생각하지 않았을때 답안
for _ in range(k-1):
    dist.remove(max(dist))
    
print(sum(dist))

6. 백준 도서관

소요시간: 분
난이도: 중(40분)

코드를 입력하세요

7. 소요시간: 분
   난이도:

코드를 입력하세요