[멀티잇 코딩테스트 러닝클래스] 그리디(Greedy) : 거스름돈, 구름 스퀘어, 직사각형 만들기 - 파이썬(Python)

거스름돈

 

 

 

 

주어진 수를 money라는 변수에 저장하고 money가 0이 될 때까지 반복문을 실행합니다. 이때 money가 40 이상이라면 money를 40으로 나눈 몫 * 40을 빼줍니다. 이러한 방식으로 money가 20 이상 40 미만일 때, 10 이상 20 미만일 때, 5 이상 10 미만일 때, 5 미만일 때를 처리해주면 됩니다.

 

 

ans = 0
money = int(input())

while money > 0 :
	cal = 0
	if money >= 40 :
		cal = money // 40
		money -= 40 * cal
	elif 20 <= money < 40 :
		cal = money // 20
		money -= 20 * cal
	elif 10 <= money < 20 :
		cal = money // 10
		money -= 10 * cal
	elif 5 <= money < 10 :
		cal = money // 5
		money -= 5 * cal
	else :
		ans += money
		money = 0
	ans += cal
	
print(ans)

 

 

그런데 다중 if문으로 작성하다보니 코드가 길어집니다. 조금 더 간결하게 바꾸어보겠습니다. coins 배열을 만들고 coins 배열 길이 만큼만 반복문을 돌려 ans에는 money를 coins의 원소로 나눈 몫을 더해주고, money는 money // coin * coin으로 초기화시켜줍니다.

 

 

ans = 0
coins = [40,20,10,5,1]
money = int(input())

for coin in coins :
	ans += money // coin
	money -= money // coin * coin
	
print(ans)

 

---

 

구름 스퀘어

 

 

 

 

time_table 배열을 만들고 주어진 행사 시작 시간과 종료 시간을 리스트 형태로 추가해주었습니다.

 

이제 time_table을 일정 기준에 따라 정렬해야 하는데요. 가장 많은 행사를 치르기 위해서는 종료 시간이 빠른 순으로 정렬하는 것이 최선의 방법입니다. 이에 따라 람다를 이용하여 종료 시간이 빠른 순으로 정렬했습니다.

 

이후 반복문을 통해 '현재 행사의 종료 시간 + 1시간'이 다음 행사의 시작 시간보다 같거나 작은지 판단하여, 만약 그렇다면 행사 수를 나타내는 변수 ans를 1 증가시킵니다.

 

 

import sys
input = sys.stdin.readline
N = int(input())
ans = 1
time_table = []

for i in range(N) :
	s,e = map(int,input().split())
	time_table.append([s,e])
	
time_table.sort(key=lambda x:x[1])

cur = time_table[0]
for i in range(1,N) :
	if cur[1] + 1 <= time_table[i][0] :
		cur = time_table[i]
		ans += 1

print(ans)

 

---

 

직사각형 만들기

 

 

 

 

만든 직사각형의 넓이의 합이 최대가 되려면 남은 막대들 중 가장 긴 막대끼리 직사각형을 만들어야 합니다. 예를 들어 주어진 막대의 길이가 [2, 4, 6, 8, 2, 4, 6, 8] 이라면, 6*8 + 2*4 = 56이 최대 넓이가 됩니다.

 

주어진 막대가 몇 번 등장하는지 나타내는 배열  cnt를 선언하여 어떤 막대가 한 번 등장할 때마다 해당 인덱스에 1을 더해줍니다.

 

이후 반복문을 통해 cnt의 어떤 인덱스의 값이 2 이상이라면, rectangle 배열에 추가시키고 해당 인덱스의 값은 2만큼 빼줍니다.

 

마지막으로 rectangle을 내림차순으로 정렬하여 가장 앞의 두 원소끼리 곱한 값을 ans에 더해주면 됩니다.

 

 

import sys
input = sys.stdin.readline
N = int(input())
sticks = list(map(int,input().split()))
cnt = [0 for _ in range(1000001)]
rectangle = []
ans = 0

for stick in sticks :
	cnt[stick] += 1

for length in range(1,1000001) :
	while cnt[length] > 1 :
		cnt[length] -= 2
		rectangle.append(length)
		
rectangle.sort(reverse=True)

for i in range(1,len(rectangle),2) :
	ans += rectangle[i-1] * rectangle[i]
	
print(ans)