당장 좋은 것만 선택하는 Greedy

거스름돈 예제

 

손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수를 구하라. 단, 거슬러 줘야할 돈 N은 항상 10의 배수이다. 

 

	price = 1260
	coin500 = 0
	coin100 = 0
	coin50 = 0
	coin10 = 0
	if((price // 500) != 0 ):
	coin500 += (price//500)
	price -= coin500 * 500
	if((price // 100) != 0):
	coin100 += (price//100)
	price -= coin100 * 100
	if((price // 50) != 0):
	coin50 += (price//50)
	price -= coin50 * 50
	if((price // 10) != 0):
	coin10 += (price//10)
	price -= coin10 * 10
	print(coin500 + coin100 + coin50 + coin10)

view raw 그리디 거스름돈 예제 - 본인 버전 hosted with ❤ by GitHub

	n= 1260
	count = 0
	# 큰 단위 화폐부터 차례대로 확인
	coin_types = [500, 100, 50, 10]
	for coin in coin_types:
	count += n // coin
	n %= coin
	print(count)

view raw 나동빈님 버전 hosted with ❤ by GitHub

    

--------------------------------------

화폐의 종류만큼 반복을 수행해야 한다. 따라서 화폐의 종류가 K개라고 할 때 위 소스코드의 시간 복잡도는 O(K)이다. 거슬러 줘야하는 돈 N은 시간 복잡도와 무관하다는 것을 할 수 있다. 

 

큰 수의 법칙

 

n개의 배열에서 주어진 수들을 m번 더하여 가장 큰 수를 만든다. 이때 특정 인덱스에 해당하는 수가 연속해서 k번까지만 더해질 수 있다. n, m k와 배열을 입력받았을 때 가장 큰 수를 출력하도록 만드시오.

	n, m, k = map(int, input().split())
	data = list(map(int, input().split()))
	data.sort() #오름차순 정렬
	result = 0
	first = data[n-1]
	second = data[n-2]
	# 가장 큰 수가 더해지는 수 계산, k+1은 주기
	count = int(m/k+1)*k
	count += m % (k+1)
	result += (count) * first
	result += (m-count) * second
	print(result)

view raw 큰 수의 법칙 - 업그레이드 hosted with ❤ by GitHub

	n, m, k = map(int, input().split())
	data = list(map(int, input().split()))
	data.sort() #오름차순 정렬
	result = 0
	while True:
	for i in range(k):
	if m == 0:
	break
	result += data[n-1]
	m -= 1
	if m == 0:
	break
	result += data[n-2]
	m -= 1
	print(result)

view raw 큰 수의 법칙 - 간단한 버전 hosted with ❤ by GitHub

--------------------------------------

숫자 카드 게임

숫자가 쓰인 카드들이 n행 * m열 형태로 놓여있다. 먼저 뽑고자 하는 카드가 포함된 행을 선택한다. 그다음 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 한다. 

 

	n, m = map(int, input().split())
	data = []
	result = 0
	for i in range(n):
	data = list(map(int, input().split()))
	min_data = 10001
	for a in data:
	min_data = min(min_data, a)
	result = max(result, min_data)
	print(result)

view raw 숫자 카드 게임 - 2중 반복문 이용 hosted with ❤ by GitHub

	n, m = map(int, input().split())
	data = []
	result = 0
	for i in range(n):
	data = list(map(int, input().split()))
	min_data = min(data)
	result = max(result, min_data)
	print(result)

view raw 숫자 카드 게임 - min() hosted with ❤ by GitHub

	n, m = map(int, input().split())
	data = []
	result = 0
	min_list = []
	for i in range(n):
	data = list(map(int, input().split()))
	min_data = min(data)
	min_list.append(min_data)
	print(max(min_list))

view raw 숫자 카드 게임 - 본인 버전 hosted with ❤ by GitHub

-------------------------------------

1이 될 때까지

어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 수행하려 한다.

1. N에서 1을 뺀다.

2. N을 K로 나눈다. 

N과 K가 주어질 때, N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하시오

 

	import time
	n, k = map(int, input().split())
	count = 0
	start = time.time()
	while True:
	if (n % k) != 0:
	n -= 1
	count += 1
	else:
	n /= k
	count += 1
	if n == 1:
	break
	end = time.time()
	print(count)
	print(end -start)

view raw 1이 될 때까지 hosted with ❤ by GitHub