[백준] 5585번 - 거스름돈 1) 문제 해결 아이디어 그리디 알고리즘의 대표적인 문제이다. for문에서 화폐단위가 큰 것부터 검사해야 총 동전 수의 최소값을 만들 수 있다. 2) 소스코드 pay = int(input()) # 지불 금액 money = [500, 100, 50, 10, 5, 1] charge = 1000 - pay # 잔돈 res = 0 # 잔돈 개수 for m in money: # 탈출 조건 if(charge == 0): break # 해당 단위로 나눠지면 if((charge // m) != 0): res += charge // m # 잔돈 개수 추가 charge %= m # 잔액 변경 print(res)
[백준] 2839번 - 설탕 배달 (풀이1) 내 풀이 1) 문제 해결 아이디어 복잡하게 소스코드를 작성하다가 한 순간 아이디어가 떠올라 수학적으로 접근하여 문제를 해결하였다. 3x + 5y = n 이라는 식을 도출했다. x, y가 모두 양의 정수인 (x, y)쌍을 찾고 그들 중에서 (x+ y)의 최소값이 정답이다. 물론 여기서 위의 조건을 만족하는 (x, y)가 없다면 이는 3, 5 봉지 종류로는 만들 수 없다는 뜻이므로 -1을 출력시켜야 한다. x = 0부터 1씩 증가시키고 y는 x 값을 넣어 계산한 후, y가 음수가 되면 반복문을 탈출한다. x, y는 모두 양수여야 하며 y가 float형으로 계산된다면 해당 x, y 쌍을 더한 값은 리스트에 넣지 않는다. 2) 소스코드 n = int(input()) ..
[백준] 11399번 - ATM 1) 문제 해결 아이디어 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값은 각 사람의 인출 시간을 오름차순으로 정렬하는 것이다. 각 사람의 인출 소요 시간은 앞 사람의 인출 소요 시간에 자신의 인출 시간을 더한 값이므로 앞 사람들의 인출 시간이 적어야 총 인출 시간이 최소가 된다. 2) 소스코드 n = int(input()) # 사람 수 times = list(map(int, input().split())) # 각 사람의 인출 시간 res = 0 # 총 최소 시간 times.sort() # 오름차순 정렬 for i in range(n): # 0 ~ i까지 더하기 for j in range(i+1): res += times[j] print(res)
[백준] 11047번 - 동전 1) 문제 해결 아이디어 사실상 최소 개수로 동전을 거슬러주는 문제와 동일하다. 동전의 가치가 큰 동전을 최대한 많이 거스는 것이 동전을 최소로 하기 위한 방법이다. 동전 종류를 큰 순서대로 내림차순하여 처리하는 것이 포인트다. 높은 금액대부터 for문으로 검사하여 동전 가치가 금액보다 작거나 같으면 몇 개를 바꿀 수 있는지 계산하여 더해주는 방식으로 구현하였다. 2) 소스코드 n, k = map(int, input().split()) # 동전 종류 수, 총 금액 coins = [int(input()) for _ in range(n)] # 동전 가치(오름차순) coins.sort(reverse=True) # 내림차순 정렬 cnt = 0 # 필요한 동전 개수 # 필요한 동전 ..
