[5문제] 그리디 문제풀이 01

m1njae·2022년 1월 9일
0

5문제

목록 보기
1/14
post-thumbnail

백준 2839번

해결 아이디어

적은 개수의 봉지를 들고 가려면 우선적으로 5킬로그램 봉지를 많이 사용해야한다. 5킬로그램 봉지를 사용하기 위해서는 설탕 N킬로그램을 5로 나누어 떨어질 수 있도록 만들어야 한다고 생각했다. 3킬로그램을 n봉지씩 빼주면서 남은 (N-3*n) 킬로그램이 5로 나누어 떨어지도록 하면 적은 개수의 봉지를 들고 갈 수 있다. 정확하게 N킬로그램을 분배할 수 없을 경우에는 -1을 출력하면 된다.

내가 작성한 코드

sugar = int(input())
count =0

while sugar>=0:
    if sugar%5 == 0:
        count += (sugar//5)
        print(count)
        break
    sugar -=3
    count +=1  
else:
    print(-1)

백준 11399번

해결 아이디어

문제 해결하는데 가장 중요한 부분은 인출하는데 걸리는 시간이 빠른 사람 순서대로 정렬시켜야 한다는 것이었다. 그 이후로는 구현의 문제였다.

내가 작성한 코드

num_people = int(input())
time = list(map(int,input().split()))
time.sort()
result = 0
for i in time:
    result = result + (i * num_people)
    num_people -= 1

print(result)

백준 11047번

해결 아이디어

거스름돈 유형의 문제였다. 필요한 동전 개수가 최소가 되려면 가장 가치가 높은 동전을 많이 활용해야한다. 동전의 가치가 오름차순으로 주어져있기 때문에 내림차순으로 변경해주어 가치가 높은 동전 우선적으로 K원에 나누어주게 하여 동전 개수를 최소화시켜 주는 방법을 택했다.

내가 작성한 코드

N,K = map(int, input().split(' '))

arr= []
count = 0
for i in range(N):
    money = int(input())
    arr.append(money)

arr.sort(reverse=True)

for coin in arr:
    count += (K // coin)
    K = K % coin

print(count)

백준 5585번

해결 아이디어

11047번과 같은 유형의 문제였다. 입력 값이 지불할 돈이기 때문에 1000엔에서 지불할 돈을 빼주어 거스름돈을 지정해주어야 한다. 돈의 종류가 많기 때문에 배열을 활용하여 문제를 해결했다.

내가 작성한 코드

n = int(input())
charge = 1000 - n
count = 0

arr = [500, 100, 50 , 10, 5, 1]

for case in arr:
    count += (charge//case)
    charge %= case
  
print(count)

백준 1026번

해결 아이디어

S의 최솟값을 구하기 위해서는 B배열에서 가장 큰 수를 A배열에서 가장 작은 수와 곱하고, B배열에서 그 다음 큰 수를 A배열에서 그 다음 작은 수와 곱하는 방식이어야 한다. 처음에는 A배열을 오름차순, B배열은 내림차순 한 후 곱하는 방식을 생각해보았지만, B는 재배열이 안되므로 다른 방법을 생각해보았다. 파이썬의 minmax를 활용해 수를 찾아내고 pop()을 통해 이미 사용한 숫자는 뽑아내는 방식으로 문제를 해결했다.

내가 작성한 코드

num = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))


S = 0
for i in range(num):
    S = S + (min(a) * max(b))
    a.pop(a.index(min(a)))
    b.pop(b.index(max(b)))

print(S)
profile
할 수 있는 것부터 차근차근, 항해자의 공부 기록공간

0개의 댓글