https://www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 1. 문제 설명 도시 개수, 도시 별 1리터 당 기름 가격, 도시에서 도시 사이의 거리를 입력받아 주유비의 최솟값을 구하는 문제다. 2. 풀이 첫 번째 시도(17점) 1. 어차피 마지막 도시에서는 더 가지 않으니 가격을 생각하지 않았다. 2. price의 최솟값을 구해 그 도시부터 마지막 도시까지 가는 거리를 더했다. 3. 최솟값 도시가 오기 전까지는 반복문을 돌면서 다음으로 갈 도..

https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 문제 풀이 그리디 알고리즘의 대표적인 유형인 거스름돈 문제와 유사하다. 동전의 개수를 최소로 만들어야 하므로 제일 큰 동전부터 거슬러주면 된다. 하지만, 만약 동전의 종류들의 모두 각각의 배수가 아니라면 이 문제는 그리디 알고리즘으로 풀 수 없다. (동전이 50원, 100원, 400원, 500원 이렇게 있다면 800원을 줘야 할 때 ..

❇️이 글은 '이것이 코딩테스트다' 교재를 학습하며 작성했습니다. 그리디 알고리즘은 현재 상황에서 가장 좋아보이는 것만을 선택하는 알고리즘이다. 1. 거스름돈 문제 당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러줘야 할 동전의 최소 개수를 구해라. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다. 해결방법 돈을 가장 큰 화폐 단위부터 거슬러주면 된다. n=1260 count = 0 #큰 단위의 화폐부터 차례대로 확인 coin_types = [500, 100, 50, 10] for coin in coin_types: count+=n//coin #해당 화폐..