1092번: 배 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보 www.acmicpc.net ** 문제 유형 그리디 ** 풀이 모든 박스를 배로 옮기는데 드는 시간의 최솟값 계산 매 분마다, 모든 크레인에 대하여 옮길 수 있는 박스를 선택하여 옮기도록 함 박스를 무게 기준으로 내림차순 정렬한 뒤에, 무거운 것부터 옮기도록 함 시간 복잡도 O(NM)에 문제 해결 가능: 크레인 개수 N, 박스 개수 M import sys n = int(input()) cranes = list(map(int, input().split())) m = int(i..

2012번: 등수 매기기 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에 걸쳐 각 사람의 예상 등수가 순서대로 주어진다. 예상 등수는 500,000 이하의 자연수이다. www.acmicpc.net ** 문제 유형 그리디 ** 풀이 예상 등수와 실제 등수의 차이를 최소화해야 함 그 방법으로 예상된 등수를 오름차순으로 정렬하면 됨 n = int(input()) array = [] # 예상 등수 answer = 0 # 불만도의 합 for _ in range(n): array.append(int(input())) array.sort() # 오름차순 정렬 수행 for i in range(1, n + 1): answer += abs(i - array[i - 1]) prin..

1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net ** 문제 유형 그리디 ** 풀이 문자열에 있는 숫자를 모두 0 또는 모두 1로 만들어야 함 문자열의 길이는 100만 이하이므로, 시간 복잡도는 O(N)에 해결해야 함 data = input() states = [0] * 2 # states[0-1]: 0-1이 연속으로 오는 집합 수 states[int(data[0])] += 1 for i in range(1, len(data)): if data[i] != data[i - 1]: # 0과 1이 바뀔 때 state..

5585번: 거스름돈 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사 www.acmicpc.net ** 문제 유형 그리디 ** 풀이 거스름 돈의 최소 개수 계산 가장 기초적인 탐욕 알고리즘 문제 유형으로, 단순히 '큰 화폐 단위' 순서대로 잔돈을 거슬러 주면 최적의 해를 구할 수 있음 changes = 1000 - int(input()) cnt = 0 for i in [500, 100, 50, 10, 5, 1]: cnt += changes // i changes %= i print(cnt)

** 탐욕 알고리즘(Greedy algorithm) 최적의 해에 가까운 값을 구하기 위해 사용됨 여러 경우 중 하나를 결정해야할 때마다, 매순간 최적이라고 생각되는 경우를 선택하는 방식으로 진행해서, 최종적인 값을 구하는 방식 알고리즘을 작성하는 일종의 전략 ** 탐욕 알고리즘의 예 1) 동전 문제 지불해야 하는 값이 4720원 일 때 1원 50원 100원, 500원 동전으로 동전의 수가 가장 적게 지불하시오. 가장 큰 동전부터 최대한 지불해야 하는 값을 채우는 방식으로 구현 가능 탐욕 알고리즘으로 매순간 최적이라고 생각되는 경우를 선택하면 됨 coin_list = [500, 100, 50, 1] def min_coin_count(value, coin_list): total_coin_count = 0 d..